代码随想录算法训练营第五十二天 | 300.最长递增子序列、674.最长连续递增序列、718.最长重复子数组

---

一、300.最长递增子序列

题目链接

代码如下：

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1); // 以每个数字为结尾的最长递增子序列至少为1int result = 0; // 这里初始化0或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); // 遍历i-1以内的所有数字，如果有比nums[i]小的，就可以在以该数字为结尾的最长递增子序列后加上1个nums[i]，组成以nums[i]为结尾的新的最长递增子序列。在i-1之前可能有很多数字小于nums[i],所以要取能组成的最长子序列}if (dp[i] > result) result = dp[i]; // 最后的结果不在dp[nums,size() - 1]中，因为可能最长的递增子序列不是以最后一个数字为结尾的，所以要取以所有数字为结尾的最长递增子序列的最大值}return result;}
};

二、674.最长连续递增序列

题目链接

代码如下：

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size(); // 若只有一个数字，直接返回1，不会继续执行；如果没有数字，直接返回0,不会继续执行。这样写是和题300保持一致，不会混淆int result = 0;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;}
};//if (nums.size() == 0) return 0;
//int  result = 1;
// 如果是这样写，result就应该初始化为1，因为如果result=0，输入只有一个数字，不会进入下面的for循环，结果输出0了，但正确应该是1。

三、718.最长重复子数组

题目链接

代码如下：

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