本文主要是介绍第五十天 进入子序列问题 | 300.最长递增子序列 674.最长连续递增序列 718.最长重复子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：300.最长递增子序列
1.dp数组的定义：
以nums[i]为结尾的最长递增子序列的长度
为什么一定表示 “以nums[i]结尾的最长递增子序” ，因为我们在 做 递增比较的时候，如果比较 nums[j] 和 nums[i] 的大小，那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾， 要不然这个比较就没有意义了，不是尾部元素的比较那么 如何算递增呢。
2.递推公式：
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值
3.初始化
对于每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1（易错）
4.遍历顺序
从小到大
5.打印dp
代码如下：
class Solution {
public:int lengthOfLIS(vector<int>& nums) {if(nums.size() == 0) return 0;vector<int> dp(nums.size(), 1);dp[0] = 1;int result = 0;for(int i = 0; i < nums.size(); i++){for(int j = 0; j < i; j++){if(nums[j] < nums[i]){dp[i] = max(dp[j] + 1, dp[i]);}}result = max(result, dp[i]);}return result;}
};最后的返回值易错：最长的结果不一定是以最后一个元素为结尾，所以需要在遍历的过程中不断更新最大值为结果，记录到result里面
题目：674.最长连续递增序列
本题相对于上一道题多了“连续”的条件。
会了上一道题，这道题ac了
思路：
1.dp数组含义：以nums[i]为结尾的最长递增子序列的长度
2.动态转移方程：
3.初始化：
4.遍历顺序：
5.打印dp数组
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if(nums.size() == 0) return 0;if(nums.size() == 1) return 1;vector<int> dp(nums.size(), 1);int result = 0;for(int i = 1; i < nums.size(); i++){if(nums[i - 1] < nums[i]){ //没有必要遍历i - 1之前的元素了dp[i] = dp[i - 1] + 1;}result = max(dp[i], result);}return result;}
};题目：718.最长重复子数组
思路：
1.dp[i][j]数组含义：
以i - 1为结尾的nums1和j - 1为结尾的nums2的最长重复子数组
这篇关于第五十天 进入子序列问题 | 300.最长递增子序列 674.最长连续递增序列 718.最长重复子数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
