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为什么这个方法成立
- 长度相同的候选中,最小尾值不会比更大尾值更难接上未来元素。
- 找到首个≥x 的位置,前一个尾值严格小于 x,因此可构造对应新长度。
- 替换保持各长度最小尾值不变量,最长有效长度就是 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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
[2,2,2] 严格 LIS 多长?
需要一点提示
相等能接吗?
查看解析与答案
1。
[5,1,6,2,3] 中 tails 会改变哪些值?
需要一点提示
逐项执行替换或追加。
查看解析与答案
[5]→[1]→[1,6]→[1,2]→[1,2,3],长度 3。
为何不能把数组排序后直接数不同值?
需要一点提示
排序改变原先后。
查看解析与答案
子序列必须保留原顺序;[3,2,1] 排序后有三项递增,但原 LIS 只有 1。