最长递增子序列
Longest Increasing Subsequence
求数组中最长严格递增子序列的长度；子序列不要求连续。
在力扣中练习题目描述
给你一个整数数组 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))吗?
解题思路
一维 DP · 以 i 结尾
dp[i] 只统计必须以 nums[i] 收尾的递增子序列
枚举所有子序列是 2^n，不能接受。关键是把状态定义在“结尾”上：dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。
如果前一个数是 nums[j]，只有 nums[j] < nums[i] 时才能接上去，接上后长度是 dp[j] + 1。所以
dp[i] = 1 + max(dp[j]) 对所有 j < i 且 nums[j] < nums[i]
自拟主例 nums = [3,1,4,2,5]。4 可以接在 3 或 1 后面，长度都是 2；5 前面有四个比它小的数，最长接出 3。
nums[2] = 4：前面比它小的有 j=0、j=1，最长接出 2。
- i
- 2
- dp[i]
- 2
dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
dp[0] = 12✓dp[1] = 12✓写入2并列最优
dp[2]=max(dp[0] + 1, dp[1] + 1)max(1 + 1, 1 + 1)=2每个数至少能自己开头，所以 dp 全部初始化为 1。外层 i 递增，内层枚举 j，保证计算 dp[i] 时所有 dp[j] 都已确定。
dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
dp[0] = 12—dp[1] = 12—dp[2] = 23✓dp[3] = 23✓写入3并列最优
dp[4]=max(dp[0] + 1, dp[1] + 1, dp[2] + 1, dp[3] + 1)max(1 + 1, 1 + 1, 2 + 1, 2 + 1)=3答案是所有 dp 的最大值，不是 dp[n-1]：最长子序列不一定以最后一个元素结尾。时间 O(n²)，空间 O(n)。
易错点
- 把 dp 初始化为 0：单个元素本身长度是 1，后续会整体少 1。
- 返回 dp[n-1]：最长子序列可能在任何位置结尾，要取全局最大值。
- 把 < 写成 <=：相等元素不能构成严格递增，会把重复值也算进长度。
贪心 + 二分 · 维护最小结尾
同样长度下，结尾越小越有前途
时间从 O(n²) 降到 O(n log n)；tails 数组不是实际的最长递增子序列，只能求长度，不能直接还原序列。
换一个状态：tails[k] 表示所有长度为 k+1 的递增子序列中，最小的结尾值。
结尾越小，后面越容易接上更大的数。遍历每个 x：
- 若 x 比所有结尾都大，直接追加，长度 +1；
- 否则用二分找到第一个 ≥ x 的位置，把它替换成 x。
例如 [3,1,4,2,5]：tails 依次变成 [3] → [1] → [1,4] → [1,2] → [1,2,5]，长度 3。
每个数做一次二分，时间 O(n log n)，空间 O(n)。注意 tails 只是“每个长度的最优结尾”，不是原序列中的真实子序列；要还原方案仍需记录前驱。
- 1tails 为空。
- 2对每个 x，二分找第一个 ≥ x 的位置。
- 3找不到则追加，否则替换该位置。
- 4返回 tails.size()。
易错点
- 用 upper_bound 而不是 lower_bound：严格递增时相等元素应替换而不是追加。
- 把 tails 当成答案序列输出：它只保证长度正确。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [3,1,4,2,5]每个数至少能自己组成长度 1 的递增子序列，所以 dp 全部先设为 1。
- n
- 5
dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
dp[0]=1查看 C++ 代码
延伸阅读
- “以 i 结尾”是子序列 DP 的通用套路；最大子数组和、乘积最大子数组也这样定义状态。
- 如果题目要求输出具体序列，需要在 DP 里额外记录前驱，或使用 O(n²) 版本回溯。