【代码随想录】day52

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

一、300最长递增子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int res = 1;
        for (int i = 1; i < nums.size(); i ++) {
            for (int j = 0; j < i; j ++) {
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

二、674最长连续递增序列

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

三、718最长重复子数组

太巧妙了，根本想不到

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int res = 0;
        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        for (int i = 0; i < nums1.size(); i ++) {
            for (int j = 0; j < nums2.size(); j ++) {
                if (nums1[i] == nums2[j]) {
                    dp[i+1][j+1] = 1 + dp[i][j];
                }
                res = max(res, dp[i+1][j+1]);
            }
        }
        return res;
    }
};

滚动数组状态压缩版：

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        int res = 0;
        vector<int> dp(nums1.size() + 1, 0);
        for (int i = 0; i < nums1.size(); i ++) {
            if (nums1[i] == nums2[0]) {
                dp[i+1] = 1;
            }
        }
        for (int j = 1; j < nums2.size(); j ++) {
            for (int i = nums1.size() - 1; i >= 0; i --) {
                if (nums1[i] == nums2[j]) {
                    dp[i+1] = dp[i] + 1;
                }
                else {
                    dp[i+1] = 0;
                }
                res = max(res, dp[i+1]);
            }
        }
        return res;
    }
};