0300. 最长递增子序列 #
- 标签:二分查找、动态规划
- 难度:中等
题目大意 #
给你一个整数数组 nums,找到其中最长严格递增子序列的长度。
解题思路 #
用动态规划来做。
动态规划的状态 dp[i] 表示为:以第 i 个数字结尾的前 i 个元素中最长严格递增子序列的长度。
遍历前 i 个数字,0 ≤ j ≤ i:
- 当 nums[j] < nums[i] 时,nums[i] 可以接在 nums[j] 后面,此时以第 i 个数字结尾的最长严格递增子序列长度 + 1,即 dp[i] = dp[j] + 1。
- 当 nums[j] ≥ nums[i] 时,可以直接跳过。
则状态转移方程为:dp[i] = max(dp[i], dp[j] + 1),0 ≤ j ≤ i,nums[j] < nums[i]。
最后再遍历一遍 dp 数组,求出最大值即可。
代码 #
|
|