最长递增子序列 · cmm✨ 的算法小课堂

最长递增子序列（LIS） 是个经典的动态规划问题：在一个数组里找一个最长的严格递增子序列（不必连续）。比如 [10, 9, 2, 5, 3, 7, 101, 18] 的一个 LIS 是 [2, 3, 7, 18]，长度 4。

DP 的核心思路

定义 dp[i] = 以 a[i] 结尾的 LIS 的长度。注意必须以 a[i] 结尾，这个约束让子问题之间能拼起来：

dp[i] = 1 + max{ dp[j] : j < i 且 a[j] < a[i] }

意思是：要算 dp[i]，就看 i 之前所有比 a[i] 小的 a[j]——它们各自的 LIS 接上 a[i] 都能变成一个以 a[i] 结尾的更长子序列，取里面最长的 +1。如果前面没人比 a[i] 小，dp[i] = 1（自己一个人也是子序列）。

光知道长度不够，还要把序列取出来。技巧是在更新 dp[i] 的同时，记下”是哪个 j 让 dp[i] 变大的”，存到 parent[i]。最后从 dp 最大的位置往回顺着 parent 走，就能拿到整条序列。

用二分查找可以做到 O(n log n)，但那是另一个故事——dp 数组的语义完全变了。教学上 O(n²) 版本更适合理解 DP 的本质。