动态规划-300.最长递增子序列-力扣(LeetCode)

白天的黑夜

发布于 2025-10-22 16:58:32

1170

文章被收录于专栏：leetcode题目解析和知识分享leetcode题目解析和知识分享

一、题目解析

子数组vs子序列

回过头来，我们分析题目给出的条件，其中要注意的是严格递增这个字眼

二、算法原理

1、状态表示

我们想要知道的是最长递增子序列长度，所以dp[i]表示：以i位置元素为结尾的所有子序列中最长递增子序列的长度

2、状态转移方程

此时我们需要另一个变量j来表示j属于[0,i-1]，在这个区间内找出以i位置为结尾的最长子序列

3、初始化

对表全部初始化为1，避免判断长度是否大于1

4、填表顺序

从左往右填表，保证所需值已被填写

5、返回值

由于dp表中记录的是[0,i]位置的最长子序列，所以只需要返回dp表中的最大值即可

来开启今日的编写代码之旅吧，链接：300. 最长递增子序列 - 力扣（LeetCode）

三、代码示例

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,1);
        for(int i = 1;i<n;i++)
        {
            for(int j = 0;j<=i-1;j++)
            {
                if(nums[j]<nums[i])
                {
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
        }
        int dp_max = dp[0];
        for(auto e : dp)
        {
            if(e>dp_max) dp_max = e;
        }
        return dp_max;
    }
};