leetcode力扣 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

提示：

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

进阶思考：

你能将算法的时间复杂度降低到 O(n log(n)) 吗? -->相关题目链接暂时

题解:

动态规划的题

f[i]

状态表示:

• 集合: 只考虑前 i 个数(包含i), 并且以第i个数结尾的子序列的所有方案
• 属性: 最大值

状态计算:

对于第 i 个数的状态转移方程是:

1. 只有一个第 i 个数, 此时f[i] = 1;
2. 以第1个数结尾的基础上再选第i个数尾结尾, 以第2个数结尾的基础上再选第i个数结尾...以第i - 1个数结尾的基础上再选第i个数结尾,上面所有情况的长度取max就是f[i], 也就是 f[j] + 1, 因为选第i个数, 所有长度加1, j 属于(0, i)

看不懂状态计算的话, 一定要多理解状态表示, 理解了状态表示, 就可以理解状态计算

ac代码👇

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() == 0) return 0;

        // 以第i个数结尾的最长上升子序列 max
        vector<int> f(nums.size(), 0);
        
        for (int i = 0; i < nums.size(); i ++)
        {
            f[i] = 1;  // 只有第i个数的情况, 也就是状态计算1

            for (int j = 0; j < i; j ++)  // 状态计算2
                if (nums[i] > nums[j]) f[i] = max(f[i], f[j] + 1);  // 要加上判断, 使子序列满足严格的单调递增
        }

        int res = 0;  // 最长上升子序列不一定会选最后一个, 也不一定会选倒数第二个..., 所有最后的答案是f数组中的最大值, 主要还是要理解状态表示
        for (int i = 0; i < f.size(); i ++) res = max(res, f[i]);

        return res;
    }
};

觉得写的不错的话, 点个赞吧~

热门相关：谎言与性2   我的抢婚老公是恋爱脑   无间   隐世王者   天师我啊真的不想吃软饭