本文主要是介绍力扣● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
● 300.最长递增子序列
1.dp数组含义。dp[i]：以nums[i]为结尾的递增子序列的最大长度。
注意一定是以nums[i]结尾，如果dp[i]定义错误的话，暴力也不知道咋整。
2.递推公式。这道题与背包的单词划分比较像，一个单层循环是弄不出来的，外层循环i，内层循环j。即当前下标i的递增子序列长度，其实和i之前的下表j的子序列长度有关系。准确的说，i的递增子序列长度就是由[0,i-1]范围内的子序列长度得到的，要取他们中的一个最大值。分析如下：
如果nums[i]比nums[j]小或者相等，那么就不能把nums[i]拼到nums[j]结尾的序列上，即不能根据dp[j]得到dp[i]，因为dp[i]一定是nums[i]为结尾的递增子序列的最大长度，nums[i]要比这个序列中的其他元素都大。
所以递推公式只考虑nums[i]比nums[j]大的情况，一开始，j=i-1，这个序列里面只有i自己，所以dp[i]=1，然后从后往前依次比较要不要加入j的子序列，有可能i加入j的这个子序列后长度更大，长度是dp[j]+1；也有可能加入后长度没变大，所以保持原样。
所以dp[i]应该取这两个的较大值：dp[i]=max(dp[j]+1,dp[i]);
代码随想录：注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值（从后往前依次比较取得的）。
公式结合例子更好理解，举例：
nums = [10,9,2,5,3,7,101,18]
到元素3的时候，dp[4]一开始是1，意味着这个子序列只有自己；与5比较比5小，不能把自己拼到5的子序列后面，即不能由dp[3]得到，跳过；与2比较，可以拼到2后面，取max为2；比9大；比10大。所以dp[4]=2。
3.初始化。dp[i]的最大长度，一开始只有它自己一个元素组成一个序列，所以均初始化为1。
4.遍历顺序。根据递推公式过程，i从左到右，j从右到左。
5.打印。
代码如下。仍然注意dp数组的含义，最后不是返回dp[nums.size()-1]，而是返回dp中的最大值。
class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> dp(nums.size(),1);int maxlen=1;for(int i=0;i<nums.size();++i){for(int j=i-1;j>=0;--j){if(nums[j]<nums[i]){dp[i]=max(dp[j]+1,dp[i]);maxlen=max(dp[i],maxlen);}}}return maxlen;}
};
● 674. 最长连续递增序列
这道题和上一道题的区别是：递增序列是连续的，那么不需要内层循环遍历[i-1,0]，因为nums[i]只能拼接到nums[i-1]上面，即根据dp[i-1]得到dp[i]，再前面的dp元素跟i扯不上关系。
所以一层循环就能实现，也不用比较max值。
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {vector<int> dp(nums.size(),1);int maxlen=1;for(int i=1;i<nums.size();++i){if(nums[i]>nums[i-1]){dp[i]=dp[i-1]+1;maxlen=max(maxlen,dp[i]);}}return maxlen;}
};
● 718. 最长重复子数组
这篇关于力扣● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
