leetcode刷题笔记-300.最长递增子序列。

题目

https://leetcode.cn/problems/longest-increasing-subsequence/description/

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1

提示

1 2	1 <= nums.length <= 2500 -104 <= nums[i] <= 104

思路

先理解题目说的两个概念

严格递增：[1,2,3,4]是严格递增，[1,2,2,3]不是严格递增；
子序列：数组中的一部分，删除某些元素后得到的序列，比如[1,2,3]数组，删除2后可以得到子序列1,3，也可以不删除元素1,2,3也是它的子序列。但是3,1或者2,1都不是这个数组的子序列，因为元素的顺序和源数组中元素的顺序不一致；

了解定义了，就可以上动态规划的思路了。

我们定义dp数组的含义为源数组中下标i和i之前的最长递增子序列的长度（这一点和第五题最长回文子串的思路类似）。易得dp数组应该全部初始化为1，即认为最开始的时候，每一位之前的最长递增子序列是他自己。

那么递推方程应该是咋样的呢？分为两种情况

当前位元素大于前一位，那么当前的最长子序列长度应该是前一位的最长子序列长度+1；
当前位元素小于前一位，说明不能沿用之前的结果，当前的最长子序列长度得保持不变；

可得递推公式dp[i] = max(dp[i], dp[j] + 1)，判断逻辑如下

if(nums[i] > nums[i-1]){
	// 大于，沿用之前的结果
	dp[i] = max(dp[i],dp[i-1]+1);
}else{
	// 小于或者等于，不对dp[i]操作
}

但是这样判断还不够，因为子序列是允许删除某些元素的，对于遍历一个数组而言，它就是允许遍历不连续，所以我们需要用两层循环来处理，外层循环i从1开始遍历nums数组（从0开始没有意义），内层循环j从0开始遍历到i-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);
		}else{
			// 小于或者等于，不对dp[i]操作
		}
	}
}

为什么我们需要用max来计算呢？因为每一次对i的递推都需要遍历i之前的所有元素才能递推出来，可能会出现前面某一位的最长递增子序列结果更大的情况，我们必须要保证得到的是最长的那一个子序列值。

同时，我们的遍历是从左往右的，当遍历到i的时候，i之前的那些元素在dp里面已经被正常计算出来最长的子序列长度了，所以我们只需要判断一次nums[i] > nums[j]，就可以沿用之前的结果了。

完整代码

现在就可以写最终的代码了

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int ret = 1;// 结果长度
        // 最开始的时候，每一位的最长子序列认为是它自己
        vector<int> dp(nums.size(),1);
        // 从1开始遍历，因为0只有一个元素，没有意义
        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);
                } 
            }
            // 更新结果最大值
            if(dp[i] > ret){
                ret = dp[i];
            }
        }
        return ret;
    }
};