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

300.最长递增子序列

要求：

可以删减任意个节点，最后保存最大的递增长度

难点：

4 10 4 8 9

如何 保证全局的视角，看到很前面的节点是否大于当前的节点，而不是仅仅记录状态

思路:

dp[n] ， 当子序列的末尾为N时，它的最大子序列长度

也就意味着，N在它的子序列中是最大的，遍历这个N之前的所有序列，如果比他们大，就+1

注意， 2 1 3， 虽然3 比1 2都大，但是为2，

如何做到这一点？

dp[i] = max(dp[i], dp[j]+1)，所以2 当时是1，1也是1，所以3是2，而不会是3

代码：

 1 // 要求：最长严格递增子序列长度 可以删除任意节点
 2 // 难点：如何全局的看到后面的情况0
 3 // 
 4 // dp[n] : 以nums[n]为结尾的最长递增子序列的长度！！！ 很重要
 5 // 
 6 // dp[i] = 因为是以I为结尾，所以需要把I之前的所有节点都遍历一下，找到目前最长的子序列长度
 7 //
 8 int lengthOfLIS(vector<int>& nums) {
 9     if (nums.size() == 1) return 1;
10 
11     vector<int>dp(nums.size(), 1);
12 
13     for (int i = 1; i < nums.size(); i++)
14     {
15         // 从而实现了全局，也就是4 10 4 8 9 的问题， dp[i] = dp[i-1]+1 ， dp[i-1]
16         for (int j = 0; j < i; j++)
17         {
18             if (nums[j] < nums[i])
19             {
20                 //很巧妙 一定要会用
21                 dp[i] = max(dp[i], dp[j] + 1);
22             }
23         }
24     }
25 
26     int result = INT_MIN;
27     for (int i = 0; i < dp.size(); i++)
28     {
29         result = result > dp[i] ? result : dp[i];
30     }
31 
32     return result;
33 }