代码随想录第五十二天——最长递增子序列，最长连续递增序列，最长重复子数组

leetcode 300. 最长递增子序列

题目链接：最长递增子序列

1. dp数组及下标的含义
   dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
2. 递推公式
   位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值
   所以`if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)
3. dp数组初始化`
   每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1
4. 遍历顺序
   从前向后遍历

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]; // 取长的子序列
}

整体代码如下：

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

时间复杂度: O(n^2)
空间复杂度: O(n)

leetcode 674. 最长连续递增序列

题目链接：最长连续递增序列
本题要求子序列是连续递增，所以只需要比较 nums[i]和 nums[i-1]

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

时间复杂度：O(n)
空间复杂度：O(n)

leetcode 718. 最长重复子数组

题目链接：最长重复子数组

1. dp数组及下标的含义
   dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]
2. 确定递推公式
   当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1
3. dp数组初始化
   dp[i][0] 和dp[0][j]初始化为0
4. 遍历顺序
   外层for循环遍历A，内层for循环遍历B

版本一：二维数组

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 res = 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;}if (dp[i][j] > res) res = dp[i][j];}}return res;}
};

时间复杂度：O(n × m)，n 为A长度，m为B长度
空间复杂度：O(n × m)

版本二：滚动数组

dp[i][j]由dp[i - 1][j - 1]推出，压缩为一维数组，dp[j]由dp[j - 1]推出。
遍历B数组的时候，就要从后向前遍历，这样避免重复覆盖

class Solution {
public:int findLength(vector<int>& A, vector<int>& B) {vector<int> dp(vector<int>(B.size() + 1, 0));int res = 0;for (int i = 1; i <= A.size(); i++) {for (int j = B.size(); j > 0; j--) {if (A[i - 1] == B[j - 1]) {dp[j] = dp[j - 1] + 1;} else dp[j] = 0; // 注意这里不相等的时候要有赋0的操作if (dp[j] > res) res = dp[j];}}return res;}
};

时间复杂度：O(n × m)，n 为A长度，m为B长度
空间复杂度：O(m)