题目
给你一个整数数组
nums，找到其中
最长严格递增子序列的长度。
输入: nums = [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长递增子序列是 [2,3,7,101]（或 [2,3,7,18]），长度 4。
进阶：你能把时间复杂度降到
O(n log n) 吗？
子序列可以跳着挑，只要保持原来的先后顺序：上面挑了
2 之后跳过
5 拿
3，完全合法。LC 300 是腾讯 DP 方向出现率第一的题，也是「动态规划状态定义」这件事最好的教材 —— 第一问考你敢不敢加锚，进阶问考你敢不敢换锚。
一、核心洞察：给状态加一个锚
先想清楚难在哪。「子序列可以跳着挑」意味着：
一个元素要不要，取决于它前面已经挑了什么 —— 这是组合问题，没法一眼贪心（局部最长接起来不一定是全局最长）。
动态规划的破局动作只有一个：
给状态加一个锚。
dp[i] = 以 nums[i] 结尾的最长递增子序列的长度。
锚一加上，问题立刻从「整段怎么挑」退化成「我接在谁后面」：一条以
nums[i] 结尾的递增子序列，去掉最后一个元素还是一条
以某个 nums[j] 结尾的递增子序列（
j < i）—— 子问题形状和原问题一模一样，只是规模更小。转移自然就出来了。
两个常见误解要排掉：
- 「
dp[i] = 前 i 个数里的最长递增子序列」？不行。那样定义出来的"最长"未必以 nums[i] 结尾，接 nums[i+1] 时你不知道它的末尾是谁 —— 转移写不出来。锚必须是"以谁结尾"。
- 为什么敢只看「结尾」？因为递增性只在相邻的两个元素之间发生作用：判断"能不能接"只需要比较末尾和新元素，中间怎么挑的不影响这个判断。
这和 LC 53（最大子数组和）是同一个动作：Kadane 的
dp[i] 也是"
以 i 结尾的最大子数组和"，而不是"前
i 个里的最大和"。
"以 i 结尾"是子序列/子数组问题里最好用的锚，没有之一。
二、拆解：转移怎么写
锚定之后，转移只有一句话：
dp[i] = 1 + max(dp[j])，其中 j < i 且 nums[j] < nums[i]；找不到这样的 j，就自己单独成串，取 1。
def lengthOfLIS(nums):
n = len(nums)
if n == 0:
return 0
dp = [1] * n # dp[i]: 以 nums[i] 结尾的最长严格递增子序列长度
for i in range(n):
for j in range(i):
if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
return max(dp)
三个要点：
- 初值是 1，不是 0：每个元素自己就是一条长度为 1 的递增子序列。初值写成 0 的话，全递减数组会返回 0；
- 内层是"往回看一遍"：每个
i 都要把 j 从 0 到 i-1 全部看一遍，不能找到一个能接的就停 —— 更长的链可能藏在后面；
- 答案是
max(dp)，不是 dp[n-1]：最长的那条链不一定以最后一个元素结尾。这是本题第一大坑（见 9.1，官方样例恰好让它看不出来）。
三、动画怎么看
动画五行：
- 横幅：左边"第几轮、在处理谁"，中间本帧动作，右边当前
dp[i] 的值；
- nums 行：橙框 = 当前的
i；绿框 = 正在回看的 j；接不上的 j 画灰虚线（"下一个数必须严格更大"）；绿底 = 本轮能接的候选；
- dp 行：每格是"以它结尾"的长度。
i 这一格在扫描中就地生长（橙虚线框，每刷新一次就变大），定型帧转金色；i 之后的格子还是虚线空壳；
- 金色链：从最优前驱一路回溯画出的那条当前最长链 —— 它就是"这条 dp 值对应的具体方案"，随扫描实时变化；
- 答案行：「目前最长递增子序列长度」只在定型帧刷新 —— 扫描中的
dp[i] 再大也不算数，这是刻意的口径：没定型就不进答案。
教科书帧有两处：
i = 5（值 7）—— 三个候选里
j = 3（值 5，dp 为 2）比
j = 2（值 2，dp 为 1）更长，链从
j = 2 换到
j = 3；
i = 6（值 101）—— 前面 6 个全部能接，一路涨到 4。最后
i = 7（值 18）打平不刷新，
全局最长停在 i = 6 —— 这正是"答案是
max(dp)"的现场演示。
四、完整推演表
以
[10,9,2,5,3,7,101,18] 为主例，每个
i 一行（对应动画的 8 个定型帧；帧与帧之间的 scan 帧逐个回看
j，共 28 个）：
最终
dp = [1,1,1,2,2,3,4,4]，答案是
4，出现在
i = 6（值 101）。金链是
2 → 5 → 7 → 101（下标 2, 3, 5, 6）。
注意两行：
i = 4（值 3）和
i = 3（值 5）的 dp 都是 2、最优前驱都是
j = 2 —— 同一个前驱可以被多个后续复用，这正是
O(n^2) 做法比暴力枚举所有子序列（
2^n 种）省时间的根本原因：
每个"以 j 结尾"的最优解只算一次，之后被所有能接上它的 i 直接查表。
i = 7 那行也值得多看一眼：
dp[7] = 4 与
dp[6] = 4 打平，全局最长没有被刷新。
如果这一帧你返回的是 dp[n-1]，答案恰好也是 4 —— 官方样例在这里是失效的（见 9.1）。
五、进阶：O(n log n)，换一套记账
O(n^2) 的瓶颈在于"以
i 结尾"这个锚：结尾有
n 种可能，想知道"谁能接上
x"只能逐个回看。想二分，就得换一个
按下标（也就是长度）记账的锚：
tails[len] = 所有长度为 len + 1 的递增子序列中，末尾元素的最小值。
这个定义自带一个关键性质：
tails 本身严格递增。反证：若
a < b 且
tails[a] >= tails[b]，把"长度为
b+1、末尾为
tails[b]"的那条子序列砍掉尾巴留前
a+1 项，它的末尾必然小于
tails[b] <= tails[a] —— 与"
tails[a] 是该长度下最小末尾"矛盾。
tails 严格递增，就
可以二分了。每来一个
x，找
第一个 >= x 的位置（
bisect_left）：
- 位置存在 → 把
tails[pos] 换成 x：长度 pos+1 这一档的末尾变得更小，对后面接数更有利，长度不变；
- 位置就是表尾之外 →
x 比所有末尾都大，追加，长度加一 —— 这是唯一能让答案变大的动作。
from bisect import bisect_left
def lengthOfLIS(nums):
tails = [] # tails[len]: 长度为 len+1 的子序列的最小末尾
for x in nums:
pos = bisect_left(tails, x) # 第一个 >= x 的位置
if pos == len(tails):
tails.append(x) # 比所有末尾都大：长度加一
else:
tails[pos] = x # 同长度下末尾更小
return len(tails)
不想用库函数，手写二分就是十几行（面试常被要求手写，顺便验证你真的懂 lower_bound）：
def lengthOfLIS(nums):
tails = []
for x in nums:
lo, hi = 0, len(tails)
while lo < hi:
mid = (lo + hi) // 2
if tails[mid] < x: # 往右收：mid 不可能是答案
lo = mid + 1
else: # 往左收：mid 可能是答案，hi 停在 mid
hi = mid
if lo == len(tails):
tails.append(x)
else:
tails[lo] = x
return len(tails)
动画里的行与 dp 版对应：横幅管进度，nums 行管当前元素，tails 行管这张"登记表"（每格标着
len k，即"长度
k+1 这一档"），绿底 = 当前二分区间，橙框 = 探针
mid，金框 = 收敛出的
pos；替换帧还会把
被换掉的旧值划掉给你看。
有一个必须主动讲的澄清：
tails 不是那条最长递增子序列本身。主例跑完
tails = [2,3,7,18]，而真实的 LIS 是
[2,3,7,101] 或
[2,3,7,18] —— 恰好像，是因为
18 替换
101 的那一步把内容改了。
tails 只是"每个长度下的最优末尾"的登记表，
它的长度才是答案，内容不可信。想拿到具体的序列本身，还是得回到 dp 版拿
parent 回溯。
六、Java 版
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
int best = 0;
for (int i = 0; i < n; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
best = Math.max(best, dp[i]);
}
return best;
}
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int size = 0; // 当前长度
for (int x : nums) {
int lo = 0, hi = size; // 在 [0, size) 里找第一个 >= x 的位置
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (tails[mid] < x) {
lo = mid + 1;
} else {
hi = mid;
}
}
tails[lo] = x;
if (lo == size) {
size++; // 追加：长度加一
}
}
return size;
}
Java 里
不建议用
Arrays.binarySearch 顶替手写二分：命中时它返回的是
某一个匹配位置（不保证最左），重复元素时语义和 lower_bound 不一致，还得对负数返回值做
-(ret + 1) 还原插入点 —— 手写十几行反而更短更稳。
七、边界情况
八、复杂度
- dp 版：时间
O(n^2)（每个 i 回看一遍 j），空间 O(n)（dp 与 parent 各一份；要重建具体序列就必须留 parent）。
- tails 版：时间
O(n log n)（每个元素一次二分），空间 O(n)（登记表最多 n 格）。
对照：暴力枚举所有子序列
O(2^n)；dp 版把"枚举组合"压成"查表"；tails 版再把"逐个回看"压成"二分"。每一步压缩的代价都是
放弃一部分信息：tails 版快，但丢掉了"具体哪条链"（内容会被覆盖）；dp 版慢，但
parent 记着完整的方案。面试先给
O(n^2) 讲透定义，再升级 tails —— 顺序别反。
九、常见坑
9.1 返回 dp[n-1]（官方样例恰好看不出来）
最长链未必以最后一个元素结尾。反例：
[1,2,3,0]，答案是 3（
[1,2,3]），而
dp[3] = 1。
官方样例 [10,9,2,5,3,7,101,18] 恰好让 dp[7] = 4 与答案相等 —— 用它自测永远发现不了这个 bug。这就是"官方样例恰好掩盖 bug"系列的第 N 例，自己测一定要带上
[1,2,3,0]。
9.2 「最长不减」与「严格递增」用了同一个二分
严格递增用
bisect_left（第一个
>= x 的位置），相等元素会
替换旧值，长度不涨；如果题目允许相等（最长
非减子序列），必须换成
bisect_right（第一个
> x 的位置）。用错的症状：
[7,7,7] 会算出 3，而严格版正确答案是 1。反过来（非减题用 bisect_left）会把相等的误替换，答案偏小。
9.3 把 dp 定义成「前 i 个里最长」
转移写不出来 —— "前
i 个里最长"的那条链末尾未知，接
nums[i] 时无从比较。
凡是"能不能接上"类的子序列问题，锚都必须落在"以谁结尾"上。定义错在这一步，后面写多久都是白写。
9.4 初值写成 0 / 忘了「自己单独成串」
dp 初值必须是 1（每个元素自己就是长度 1 的子序列）。初值 0 时全递减数组返回 0；
max(dp) 在空数组上会抛异常，入口先判空。
9.5 把 tails 当成 LIS 本身拿去用
tails 的内容会被覆盖（主例的
101 被
18 换掉），
只有长度是可靠的。要在 tails 版上重建具体序列，得额外记录"每个元素写入时的前驱 + 每个长度的最新末端"，代码量立刻翻倍 —— 真要序列就用 dp 版的
parent 回溯，两条路线各取所需。
9.6 手写二分的边界
hi 初值是
len(tails)（开区间），
mid 偏向左（
(lo + hi) // 2），
tails[mid] < x 时
lo = mid + 1、否则
hi = mid —— 三个细节凑齐才不会死循环。
mid 写成
(lo + hi + 1) // 2 配上
hi = mid 就是经典死循环；
hi 初值写成
len(tails) - 1 会漏掉"追加到表尾"的情形。
十、面试怎么答
- 先答 O(n^2)，把锚讲清："
dp[i] 是以 nums[i] 结尾的最长严格递增子序列长度，转移是接在前面某个更小的 dp[j] 后面，答案是 max(dp) 而不是 dp[n-1]。"
- 主动点出官方样例的盲区："这组样例恰好让
dp[n-1] 等于答案，[1,2,3,0] 才能测出'返回 dp[n-1]'的 bug。" —— 这句是区分背题和做题的分水岭。
- 再升级 O(n log n)：换锚 —— "按长度记账，
tails[len] 存该长度下的最小末尾；它严格递增所以能二分；每个元素一次 bisect_left，答案是 tails 的长度。"
- 主动澄清 tails 不是 LIS：内容被覆盖，长度才是答案；要具体序列回 dp 版拿
parent。
- 报变体：最长非减用
bisect_right；要数方案数是 LC 673（再开一个计数数组）；二维套娃是 LC 354（按宽排序后归约到本题）；同族还有 LC 1143（最长公共子序列）—— 值互异时 LIS 等价于"原序列与排序后的自己求 LCS"，两题是一家人。
- 给复杂度对照：暴力
O(2^n)、dp O(n^2)、tails O(n log n)，以及各自丢掉了什么信息。
结语
最长递增子序列是"状态定义决定一切"的定型题：
第一问考的是敢不敢给 dp[i] 加上"以 i 结尾"这个锚 —— 加上，转移自己长出来；第二问考的是敢不敢把这个锚换掉 —— 换成"按长度记账"，二分才进得来。 同一个题目的两次破局，方向完全相反：一次是把状态钉得更死，一次是把状态换得更活。前面 LC 53 的 Kadane 用过第一种，这一篇把两种都凑齐了。下一站大概率是 LC 673：同一个锚上再挂一个计数器，从"最长是多少"走到"最长有几条"。