算法训练day56leetcode300.最长递增子序列674最长连续递增序列

part13leetcode300.最长递增子序列674最长连续递增序列 718最长重复子数组

300. 最长递增子序列

本题最关键的是要想到dp[i]由哪些状态可以推出来，并取最大值，那么很自然就能想到递推公式：dp[i] = max(dp[i], dp[j] + 1);

#include <iostream>
#include <vector>

class Solution {
public:
    int lengthOfLIS(std:: vector<int>& nums) {
        std::vector<int> dp(nums.size(), 1);
        int max = 1;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = std::max(dp[i], dp[j] + 1);
                }
            }
            max = std::max(max, dp[i]);
        }
        //打印dp数组
        // for(int i: dp) {
        //     std::cout << i << ' ';
        // }
        return max;
    }
};

int main() {
    std::vector<int> nums = {10,9,2,5,3,7,101,18};
    Solution sol;
    int res = sol.lengthOfLIS(nums);
    std::cout <<std::endl;

    std::cout << "res:" << res << std::endl;
    return 0;
}

674. 最长连续递增序列

因为本题要求连续递增子序列，所以就只要比较nums[i]与nums[i - 1]，而不用去比较nums[j]与nums[i] （j是在0到i之间遍历）。

既然不用j了，那么也不用两层for循环，本题一层for循环就行，比较nums[i] 和 nums[i - 1]。

#include <iostream>
#include <vector>

class Solution {
public:
    int findLengthOfLCIS(std::vector<int>& nums) {
        std::vector<int> dp(nums.size(), 1);
        int max = 1;
        for (int i = 1; i < nums.size(); i ++) {
            if(nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            max = std::max(max, dp[i]);
        }
        //print dp
        // for (int i : dp) {
        //     std::cout << i << ' ' ;
        // }
        return max;
    }
};

int main() {
    Solution sol;
    std::vector<int> nums = {1, 2,3 ,5,2,4,6,8,7};
    int res = sol.findLengthOfLCIS(nums);
    std::cout << res << std::endl;
    return 0;
}