专题进阶 · 动态规划推荐总顺序 · 第 69 / 148 课

先建立以位置结尾的 DP,再推导各长度最小尾值的二分优化。

先学会这些,再进入本课 一维 DP 二分查找
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 动态规划

最长递增子序列LIS

基础 DP 比较所有前驱为 O(n²),维护各长度最小尾值可优化到 O(n log n)。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

先建立以位置结尾的 DP,再推导各长度最小尾值的二分优化。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

数组 [3,1,2,5,4] 的最长严格递增子序列长度是多少?子序列可跳过元素,但不能改变顺序。

02一步步得到方法

先写容易验证的平方算法

dp[i] 表示必须以 a[i] 结尾的最长递增子序列长度。遍历 j<i 且 a[j]<a[i],取 dp[j]+1 的最大值;没有可接前驱时为 1。最终答案是 max(dp),不一定在最后位置。

这个算法 O(n²),状态含义清楚,也可作为更快算法的独立参考。不要把连续子数组和允许跳跃的子序列混淆。

换一种状态,保留最有希望的尾部

tails[k] 表示长度 k+1 的递增子序列能达到的最小尾值。长度相同,尾值越小,未来可接的值就越多,因此较大尾值被支配。tails 自身严格递增。

遇到 x,找第一个≥x 的位置替换;若不存在就追加。这是 bisect_left。tails 记录不同长度各自最优尾值,组合起来未必是一条实际子序列;只求长度时无需恢复路径。

最小尾值是更容易扩展的代表

对同一长度的递增子序列,尾值越小,未来可接上的元素集合越大。因此 tails 只保存各长度中最小尾值,就能保留计算最长长度所需的信息。

tails 的不同位置可能来自不同选择路径,所以整个 tails 不保证是原数组中的一条真实子序列。若要输出路径,需要额外记录每个元素的前驱与各长度代表的下标。

03把一个小例子完全算清楚

[3,1,2,5,4]。

步骤计算与状态为什么这样做
读 3、1[3] → [1]同长度尾值变小
读 2[1,2]可延长
读 5[1,2,5]长度变 3
读 4[1,2,4]长度不变,未来更易延长

窄屏可左右滑动表格,阅读完整计算与理由。

最长长度为 3,例如 [1,2,5] 或 [1,2,4]。

04为什么这个方法成立

  1. 长度相同的候选中,最小尾值不会比更大尾值更难接上未来元素。
  2. 找到首个≥x 的位置,前一个尾值严格小于 x,因此可构造对应新长度。
  3. 替换保持各长度最小尾值不变量,最长有效长度就是 LIS 长度。

05把推导翻译成代码

Python · 可独立运行的教学实现

from bisect import bisect_left
def lis_length(a):
    tails = []
    for x in a:
        i = bisect_left(tails,x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

逐个理解关键决定

bisect_left(tails,x)
找到首个≥x,相等只替换不增长,保证严格递增。
tails[i] = x
更新状态摘要,不是修改原数组中的答案路径。

06时间、空间与实现范围

n 次二分,时间 O(n log n),tails 空间 O(n)。

恢复一条实际 LIS 需保存每个位置的前驱和对应尾部下标,不能直接返回 tails。

07改变条件,检查哪里会出错

用 bisect_right 求严格递增

它会把相等值放到后面,得到最长不下降子序列语义。

直接把 tails 当作答案序列

它可靠地给出长度与可扩展边界,恢复实际序列需要前驱记录。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

[2,2,2] 严格 LIS 多长?

需要一点提示

相等能接吗?

查看解析与答案

1。

练习 2 · 边界与辨析

[5,1,6,2,3] 中 tails 会改变哪些值?

需要一点提示

逐项执行替换或追加。

查看解析与答案

[5]→[1]→[1,6]→[1,2]→[1,2,3],长度 3。

练习 3 · 变式与迁移

为何不能把数组排序后直接数不同值?

需要一点提示

排序改变原先后。

查看解析与答案

子序列必须保留原顺序;[3,2,1] 排序后有三项递增,但原 LIS 只有 1。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。