type
status
date
slug
summary
tags
category
icon
password
最长递增子序列
给你一个整数数组
nums ，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，
[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列
示例 1：
示例 2：
示例 3：
提示：
1 <= nums.length <= 2500
104 <= nums[i] <= 104
进阶：
- 你能将算法的时间复杂度降低到
O(n log(n))吗?
思路
方法一：动态规划
动态规划五步走：
1、确定dp数组以及下标的含义
dp[i] 表示：以 nums[i] 为结尾的最长子序列长度。
2、确定递推公式
每轮计算新dp[i]时，都遍历dp[0]~dp[i−1] 数组区间，我们用dp[j]来表示当前记录当前遍历的元素，
- 如果 nums[i]>nums[j]，nums[i] 可以接在 nums[j] 之后，此时0~i的最长递增子序列长度为dp[j]+1
- 如果 nums[i]<=nums[j]，说明nums[i] 不可以接在 nums[j] 之后，跳过。
- 走完整个循环，记录满足条件的dp[j]最大值。
- 得出 dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)
3、dp数组如何初始化
dp[0]=1即可。
4、确定遍历顺序
i 从 0 到 nums.length。
方法二：贪心 + 二分查找
- Author:Zinphy
- URL:https://zouysay.cn/article/1c1bfc10-342b-458a-9e26-3619d248c3ba
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!