leetcode力扣 300. 最长递增子序列 II

给你一个整数数组 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
-1e4 <= nums[i] <= 1e4

进阶思考：

你能将算法的时间复杂度降低到 O(n log(n)) 吗?

题解:

一共有两种写法: 第一种的时间复杂度是O(n ^ 2), 第二种的时间复杂度是O(n * logn)

第一种写法：

动态规划的题

f[i]: 只考虑前 i 个数(包含i), 并且以第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代码