LeetCode 300. 最长递增子序列

最长递增子序列

题目链接:

300. 最长递增子序列

题目描述:

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

题目解析

在这个之前,我们说一下什么是子序列,我们可以将子序列看成数组的子集, 只不过这个子集有一定的要求,我们原本元素的相对位置是不能够改变的.例如下面的这样

这道题目我们求最长的子数组很相似,思路也是类似的.题目求的是我们数组的最长的子序列的长度.

算法原理

还是按照经验,我们这里仍旧按照之前的想法来.

• 以…为结尾
• 以…为开始

状态表示

根据题目分析,我们选择以…为结尾表示状态.那么我们的状态这样表示

dp[i]:表示以i位置为结尾,我们序列的最大长度

状态转移方程

这里进行分析,我们这里存在两个选择.

• 一个元素单独作为子序列, 那么dp[i] = 1
• 和前面的元素打配合共同构成子序列, 那么此时我们需要遍历我们的前面的dp

解释一下我们第二个选择, 我们直到子序列是可以不连续的,那么此时我们就会出现这样的情况.

那么遍历我们前面的结果,此时我们需要找到前面的最大值.

初始化

初始化就简单了,我们这里直接初始为1可以,默认是第一个情况.

填表顺序

从左向由填.

返回值

题目要求的最大长度,那么我们这里使用一个变量保存最大就可以了.

编写代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int result = 0;
        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]);
                }
            }
            result = max(result,   dp[i] );
        }
        return result;
    }
};