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 }