Day52 | 300.最长递增子序列, 674. 最长连续递增序列, 718. 最长重复子数组

一般来说子序列默认不连续，子数组默认连续！

最长递增子序列

LeetCode题目：https://leetcode.cn/problems/longest-increasing-subsequence/

因为所求是子序列，因此不要求连续。dp[i]设定为当到达下标为i的位置时，所得到的最长子序列长度。因为不连续，所以每次进行下标更新后，应该对之前的数值进行一次遍历。所以可以得到递推公式，当符合严格自增条件后，i下标位置长度应该是j下标位置长度+1.即if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

代码如下：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int result = 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);
            }
            if (dp[i] > result) result = dp[i];
        }
        return result;
    }
};

最长连续递增序列

LeetCode题目：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/

连续递增其实可以看做是非连续的简化版本，因为如果不符合递增条件，就需要重新开始，因此不需要进行额外的再次遍历。

最终代码如下：

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

最长重复子数组

LeetCode题目：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/

由于求解的是两个数组中的最长重复子数组。首先，因为是在两个数组内部进行求，涉及到了两个维度，因此需要构建二维dp，分别代表在第一个数组下标在i位置，且第二个数组下标在j位置时候，所存在的最长重复子数组。

也因此，确定递推公式需要进行两次循环，一层循环nums1数组，另一层循环nums2数组，以确保情况符合。同时，由于是求子数组，所以一定是要求连续的序列，只有符合两个值相等的情况下才可以进行。所继承的状态为上一次nums1[i]和nums2[j]相等的情况时的长度值，i和j同时向前进一位，即dp[i][j] = dp[i - 1][j - 1] + 1;

最终代码如下：

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

Foolish鱼