给你一个整数数组 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 个数的状态转移方程是:
- 只有一个第 i 个数, 此时f[i] = 1;
- 以第1个数结尾的基础上再选第i个数尾结尾, 以第2个数结尾的基础上再选第i个数结尾...以第i - 1个数结尾的基础上再选第i个数结尾,上面所有情况的长度取max就是f[i], 也就是 f[j] + 1, 因为选第i个数, 所有长度加1, j 属于(0, i)
看不懂状态计算的话, 一定要多理解状态表示, 理解了状态表示, 就可以理解状态计算
ac代码
标签:状态,结尾,nums,300,个数,力扣,int,序列,leetcode From: https://www.cnblogs.com/xxctx/p/18214239