Shouyu

Appearance

最长上升子序列 ​

题目描述 ​

给你一个整数数组 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 。

题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/

文章讲解：https://programmercarl.com/0300.最长上升子序列.html

思路 ​

递增子序列问题是经典的动态规划解决的问题。如果我们还记得 摆动序列 的动规解法的话，应该记得我们要想使一个摆动序列长度增加，需要明确这个序列的最后一个数是上升还是下降。

如果上升我们称作上升摆动子序列，要使上升摆动子序列长度增，必须增加一个下降的数。这样变为下降摆动子序列

如果下降我们称作下降摆动子序列，要使下降摆动子序列长度增加，必须增加一个上升的数。这样变为上升摆动子序列

那么对于这道题，要想使 递增子序列 长度增加，必须确定最后一个数是递增子序列的一部分。然后再在这个递增子序列上增加看看能不能使长度增加。这样状态之间就有关联了

动规五部曲 ​

1、dp数组及下标含义 ​

dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

2、递推公式 ​

既然 i 一定是末尾，那么他的长度一定等于前面长度+1，那么前面长度可能有多少呢？

前面长度只能从[0,i-1]中取，因此 前面长度只可能是 dp[0], dp[1], ... , dp[i-1]中的任何值。然后取最大就可以了。我们可以假设 j 从 0 到 i-1。dp[i] = dp[i] > dp[j-1] +1 ? dp[i] : dp[j-1] +1

另外就需要注意，必须满足 nums[i] > nums[j]，这时 dp[i] 才能被计算，

3、dp数组初始化 ​

从定义上看，每个递增子序列长度至少包括自身，因此为 1。

4、确定遍历顺序 ​

i 从前向后，j 从前向后。

5、举例推导 ​

输入：[0,1,0,3,2]，dp数组的变化如下：

300.最长上升子序列

因为我们定义的 i 是递增子序列的末尾，因此不能直接返回 dp[nums.size()-1] 作为结果。因为最后一个元素不一定是最长的递增子序列的末尾元素，因此我们把每个元素都当做结尾计算出来，找到最大值。因此可以在遍历中找到最长的哪个递增子序列。

代码实现 ​

C++
int lengthOfLIS(vector<int>& nums) {
    if (nums.size() <= 1) return 1;
    vector<int> dp(nums.size(),1);
    int result = 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[j] + 1,dp[i]);
        }
        result = max(result,dp[i]);
    }
    return result;
}