最长递增子序列
先学习 O(n^2) DP，再掌握 O(n log n) 技巧
最长递增子序列 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
什么是 LIS
子序列会保留元素顺序，但可以跳过元素。最长递增子序列就是其中严格递增的最长序列。
a = [3, 1, 4, 1, 5, 9, 2]子序列，而不是子数组
与子数组不同，LIS 不需要连续。您可以跳过较小的数字，让这条序列继续增长。
O(n^2) DP 状态
令 dp[i] 表示在下标 i 处结束的 LIS 长度。每个元素单独都至少构成长度为 1 的子序列。
dp = [1] * nO(n^2) 状态转移
对于每个 i，检查所有更早的 j。如果 a[j] 更小，就进行扩展：dp[i] = max(dp[i], dp[j] + 1)。
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)读取答案
结果是表中的最大值，因为 LIS 可以在任意位置结束，不一定在最后一个下标处结束。
answer = max(dp)为什么 O(n^2) 会超时
双重循环的开销是 O(n²)。当 n 接近 100000 时，这会慢得无法接受，并得到超出时间限制的判定。
耐心排序的思路
更快的方法会为每个子序列长度维护一个可能的最小末尾值列表，思路类似耐心排序。
tails = []使用二分查找确定位置
对于每个数字，使用 bisect_left 在末尾值中进行二分查找，确定它应放置的位置，总复杂度为 O(n log n)。
from bisect import bisect_left扩展或替换
如果位置超出末尾，就使用 append 扩展 LIS。否则，用更小的值覆盖该位置的末尾值。
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x长度保存在 tails 中
扫描结束时，len(tails) 就是 LIS 的长度。这个列表本身不一定就是该子序列，只有它的长度是准确的。
answer = len(tails)严格递增与非递减
对于非递减版本，请改用 bisect_right，这样相等的值也可以扩展序列。
from bisect import bisect_right快速检查
哪种方法可以在 O(n log n) 时间内找到 LIS 的长度？
回顾：从 n^2 到 n log n
现在您有两种方法可以求解 LIS。O(n^2) DP 很简单；末尾值加二分查找的方法可以处理大规模输入，并避免超出时间限制。
常见问题解答
「最长递增子序列」课时是免费的吗？
是的 — 「最长递增子序列」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「最长递增子序列」这节课中我会学到什么？
先学习 O(n^2) DP，再掌握 O(n log n) 技巧 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「最长递增子序列」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。