最近在系统过动态规划专题刷到最长递增子序列Longest Increasing Subsequence简称 LIS这道题时我特意停下来多花了些时间。倒不是因为它难恰恰相反它是动态规划里非常适合用来理解“状态设计”和“优化方向”的入门经典。网上的题解很多但大部分只是给出转移方程和代码少有讲清楚“为什么这么设计状态”“为什么二分优化是对”的。这篇文章我把自己的完整思考过程记录下来包括朴素 DP 的推导、二分的优化思路、正确性证明、常见变体以及我在实际做题中踩过的几个有意思的坑。如果你正在准备算法面试或者刚开始接触动态规划这篇文章应该能帮你把这道题吃透。1. 问题定位与前置分析1.1 题目到底在问什么先看一个标准定义给定一个无序的整数数组找到其中最长的严格递增子序列的长度。注意几个关键词——“子序列”不是“子数组”它不要求元素在原数组中连续但元素的相对顺序不能改变。比如[1, 2, 3]是数组[3, 1, 2, 0, 3]的子序列而[3, 1]就不是因为它在原数组中是逆序的。另一个容易踩坑的关键词是“严格递增”。严格递增意味着nums[j] nums[i]而不是。如果题目改成“非递减”那在边界处理和二分查找的细节上会有一处关键差异后面我单独说。这个问题有意思的地方在于它表面上看起来像是一个“找最长”的暴力搜索问题但因为元素之间没有连续性限制子序列的数量是指数级的。拿一个长度为 n 的数组来说子序列总数是 2^n暴力枚举根本不现实。这就是我们需要动态规划或贪心加二分这类优化算法的根本原因。1.2 为什么动态规划能派上用场动态规划能解决的问题通常有两个关键特征重叠子问题和最优子结构。LIS 恰好两个都占。从最优子结构来看如果我们已经知道了nums[0..i]这个前缀的某个信息能否直接推导出nums[0..i1]的答案能但有个关键点——光是知道“前缀的最长递增子序列长度”是不够的。比如数组[4, 5, 1, 2]前缀[4, 5]的 LIS 长度是 2末尾元素是 5而前缀[4, 5, 1]的 LIS 长度仍然是 2但末尾元素变成了 1子序列是[4, 5]或[1]都可以。这时候如果给数组新增一个元素3最终 LIS 是[1, 2, 3]长度为 3。如果我们只记录“前缀 LIS 长度”这个信息就丢掉了一个关键信息不同长度的递增子序列的末尾元素最小值。所以状态设计的核心困境在于我们要在“记录什么”和“怎么转移”之间找到一个合适的平衡。不同的问题有不同的解法LIS 的经典做法是固定“以某个元素作为子序列的结尾”。1.3 从暴力搜索到记忆化搜索很多人一上来就看 DP 解法我可以理解但如果你从来没自己推过暴力搜索直接看转移方程多少有点悬空。把暴力递归写出来你才能直观感受什么叫“重叠子问题”。暴力思路很简单从每个位置出发尝试它后面所有比它大的元素递归找最长。用递归函数f(i)表示“以nums[i]作为子序列最后一个元素的最长递增子序列长度”那么def dfs(nums, i): res 1 for j in range(i 1, len(nums)): if nums[j] nums[i]: res max(res, 1 dfs(nums, j)) return res这个写法的时间复杂度是 O(2^n)因为每个元素都有“选”和“不选”两条路。但仔细观察会发现很多子问题是重复的——例如dfs(5)可能在多个递归分支里都被反复计算。用一个数组把dfs(i)的结果存起来就是记忆化搜索时间降到 O(n^2)。不过记忆化搜索本质还是递归有栈溢出风险而且代码也比迭代麻烦。在实际刷题中我更喜欢直接写迭代 DP但理解记忆化搜索能帮你确认“状态定义是自洽的”。这也是我把暴力方案写出来的原因。2. 朴素动态规划O(n²) 解法详解2.1 状态定义与转移方程现在直接给出经典解法。定义dp[i]为“以nums[i]结尾的最长递增子序列的长度”。注意这个限定——“以nums[i]结尾”这是整个状态设计的灵魂。为什么要这么定义因为我们面对的是一个无序数组不能像连续子数组那样直接比较相邻两个位置。但如果我们把视角固定在“当前元素作为子序列的最后一个元素”上那么前面只需要考虑那些值比它小的元素即可。这样转移关系就清晰了dp[i] max(1, max(dp[j] 1 for j i if nums[j] nums[i]))1是保底值因为单个元素本身就是一个长度为 1 的递增子序列。如果前面没有任何元素比nums[i]小那dp[i]就只能等于 1。这里我特别想强调一个初学者容易踩的坑dp[i]并不是“数组前 i 个元素中 LIS 的长度”而是“以第 i 个元素结尾的 LIS 长度”。这两个定义看着很像实际差别巨大。如果把dp[i]当成“前 i 个元素的最优解”你会在转移时试图跨过元素任意组合方程就写不出来就算硬写也会丢掉“递增”这个顺序约束。正确答案是dp[i]算完之后整个数组的 LIS 长度是max(dp[0..n-1])而不是dp[n-1]。这个误区几乎是每个初学者都踩过的我当年也不例外总是下意识以为最后一个状态就是全局最优实际上 LIS 的最长子序列不一定包含最后一个元素。比如数组[10, 9, 2, 5, 3, 7, 101, 18]最长子序列是[2, 3, 7, 101]或者[2, 5, 7, 101]末尾元素是101而不是18所以答案在dp[6]而不是dp[7]。2.2 核心代码实现与时空复杂度用 Python 写朴素 DP 非常简洁def length_of_lis(nums): n len(nums) if n 0: return 0 dp [1] * n for i in range(1, n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)内层循环要扫描i之前的所有元素所以总时间是1 2 ... n - 1也就是 O(n^2)。空间只用了一个长度为 n 的dp数组O(n)。如果你需要同时输出最长递增子序列本身而不仅仅是长度可以在每次更新dp[i]时记录一个prev[i]数组存下“上一个元素的下标”。最后从dp值最大的那个下标开始沿着prev往前回溯就能还原出具体的子序列。不过要注意这样还原出来的只是“某一个”最长递增子序列不是唯一的。在实际面试中面试官更常问的是“能否用二分优化到 O(n log n)”这就是下一节的内容。2.3 朴素 DP 的局限与优化动机O(n^2) 在 n 较小时完全够用比如 n 1000 时就是一百万次操作。但很多在线测评系统的数据范围是 n 10^5 甚至 10^6O(n^2) 就会超时。面试中如果候选人能主动提出“这个问题可以用贪心加二分优化到 O(n log n)”会是一个很加分的信号。但我要提醒一点不要因为学会了二分优化就完全轻视朴素 DP。二分优化的代码更短但理解门槛更高朴素 DP 虽然慢但它的状态转移关系更加直观。从学习路径来看先完全理解朴素 DP再理解优化方案才是合理的顺序。我自己在给同学讲这道题时发现一个有趣的现象直接看二分优化的解法很多人能背下代码但问他“为什么二分能保证正确”就答不上来。这说明没有建立起从朴素到优化的思维演化路径。3. 贪心 二分O(n log n) 优化方案3.1 核心思想保存“最有潜力的子序列”优化的关键思路是我们维护一个数组tails其中tails[k]表示“长度为 k1 的递增子序列中最小的末尾元素值”。注意这里说的是“最小的末尾元素值”而不是“某个具体的子序列”。为什么只关心末尾元素的最小值因为对于同样长度的递增子序列末尾元素越小后面就越容易接上更大的元素这个子序列的“扩展潜力”就越大。举个例子数组[2, 3]和[1, 3]都是长度 2 的递增子序列假设后面要接4两者都能接但如果后面是2那么只有[1, 2]能续上[2, 3]不行。所以对于长度相同的子序列末尾值越小的越值得保留。这本质上是一种贪心策略我们要维护的是“最优的”长度为 k 的子序列贪心在末尾元素上做了选择把更大的末尾值丢弃。这种做法的正确性需要严格证明但直觉上非常合理。用一句大白话总结相同长度尾巴越小越有前途。3.2 tails 数组与二分查找的配合现在的问题是如何高效维护tails数组当扫描到一个新元素x时我们要在tails中找一个合适的位置。具体规则是如果x比tails中所有元素都大说明x可以接在目前最长子序列的后面形成一个更长的子序列所以把x追加到tails末尾。否则在tails中找到第一个大于等于x的元并替换它。这一步利用了一个重要的性质tails数组本身就是严格递增的所以可以用二分查找。这段描述是网上最常见的解释但只说“找到并替换”是不够的如果没有解释“为什么可以替换”你就没有真正掌握它。替换的本质是用x作为新的末尾元素代表一个“更有潜力”的同长度子序列。而这个替换不会破坏tails的有序性因为x肯定小于被替换的那个元素且大于等于它前面的元素这是二分查找保证的。所以tails始终是有序的也就能继续二分。用生活化的类比来解释比如你是教练要组建一支递增序列的“队伍”tails[k]记录的是“第 k 个位置的队员里最矮的那一个”。如果有新人来他比当前队伍里的某个人矮但又不是太矮就让他顶替那个身高相近的队员。队伍长度没有立刻变长但队伍的整体平均身高拉低了未来更容易吸收高个子队员。这就是为什么二分法能找到问题的最优解——我们一直在用“更小末尾”换掉“较大末尾”而不改变队伍长度。3.3 标准代码与正确性论证下面是 Python 实现import bisect def length_of_lis(nums): tails [] for x in nums: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)bisect_left是关键。它的语义是在tails中找到第一个大于等于x的位置。对于严格递增子序列遇到一个与x相等的元素时不需要替换它因为“同值替换”对后续没有帮助反而可能破坏严格递增的语义。这段代码为什么是正确的我们需要从两个层面来论证第一tails的长度等于当前已经找到的最长递增子序列长度。这一点可以通过数学归纳法证明初始tails为空长度为 0每次如果x大于tails中所有元素长度加 1否则长度不变但某个位置的值变小。长度变化的时机对应着真正孕育出了更长子序列。第二tails数组严格递增。这一点通过bisect_left的定位规则来保证替换位置pos满足tails[pos-1] x tails[pos]边界条件除外替换后有序性依然成立。再加上多加的每轮判断tails的整体严格递增性质不会破坏。这两点证明不算复杂但第一次看到时很容易忽略它们。尤其是第二点如果新手用的是bisect_right或者没有考虑x与已有元素相等的情况很可能会得到错误的答案。所以我把代码里的bisect_left单独拎出来强调一下这是细节所在。3.4 为什么二分法返回的是长度而不是具体子序列很多人在学习这个优化时会产生一个疑问tails最终的内容并不是某个真正的递增子序列那答案长度还可靠吗问得好。tails数组的每一个位置确实都来自某个子序列的末尾元素但这些元素拼在一起并不一定构成一个合法子序列它们分属不同的“候选序列”。比如数组[3, 1, 2]最终tails [1, 2]这恰好是一个合法子序列但换个例子[2, 1, 3]最终tails [1, 3]虽然[1, 3]在原数组里它也是合法的1 在 3 前面但更复杂的情况下tails的某些值来自不同的分支。比如[1, 3, 0, 2, 4]最终tails [0, 2, 4]这个序列在原数组中并不存在0 在 2 后面不在前面。因此tails不是真正的答案序列它只是一个“状态记录器”。我们只信任它的长度不信任里面的具体值。如果你需要还原出真正的递增子序列最稳妥的办法是回到朴素 DP 加上prev指针或者用另一种“耐心排序”变体来记录每个位置对应的原数组下标和前缀信息。不过在绝大多数只需要长度的场景里tails方案已经足够。4. 变体问题与实战进阶4.1 最长非递减子序列面试和竞赛中一个最常见的变体是把“严格递增”改成“非递减”。此时相邻相等是允许的所以状态转移条件从nums[j] nums[i]变成nums[j] nums[i]。对应的二分优化也要改一行bisect_left改为bisect_right。为什么因为对于严格递增新来的x如果与tails[pos]相等替换它是没有意义的严格递增不允许相等但对于非递减相等的值可以接在已有序列后面所以新来的相等元素应该被追加到“相同值的后面”这样才能扩展长度。这个细节是面试官非常喜欢挖的考点。如果你能直接说出这个区别对方就知道你真的理解了这个算法而不只是背了代码。4.2 二维变体俄罗斯套娃信封问题我最初完全没有意识到 LIS 的扩展空间这么大直到碰到“俄罗斯套娃信封问题”。题目要求你求最多能套多少层信封每个信封有宽度和高度套娃的条件是宽度和高度都严格大于内层信封。解法是先按宽度升序排序宽度相同时按高度降序排序。然后对高度数组求 LIS。这里的高度降序是一个精妙的设计宽度相同的信封不能互相套入按降序排列可以让这些信封在求 LIS 时天然不可互选因为后序信封的高度都小于或等于前序不会被选入递增序列。这类“排序 LIS”的组合技巧是动态规划进阶的常见套路。4.3 LIS 在工程中的现实场景有人可能会问这道题除了面试实际工程里有价值吗答案是有的。一个典型的应用是“最小插入次数让数组有序”。给定一个几乎有序的数组我们希望尽可能少地移动元素使其变成严格递增。那么只需要找到原数组中的 LIS其他元素就是需要移动的。这个思路在一些数据处理管道里的有序性修复、增量排序策略中很常见。另一个场景是基因序列分析。在生物信息学中比较两条 DNA 序列的相似度时本质上是找它们的“最长公共子序列”LCS而 LCS 可以规约到 LIS 问题。如果你对算法竞赛比较熟悉应该知道“最长公共子序列转 LIS”这个经典技巧——通过将其中一个序列的每个元素映射到它在另一个序列中的位置按降序排列以避免选中多个相同元素就转换成了 LIS 问题。4.4 输出具体子序列的两种方案说了这么多可能有人已经发现一个问题二分优化只给长度不给子序列本身。如果题目既要求长度又要求打印具体序列该怎么办方案一用朴素 DP 加入prev数组O(n^2) 时间换取完整路径。适合 n 较小的情况。方案二在二分优化的基础上额外维护一个pos_idx数组记录每个tails位置对应的原数组下标同时维护prev数组记录每个下标的“前驱下标”。这样在遍历完所有元素后可以回溯得到完整子序列。这种方案的时间复杂度仍然是 O(n log n)但要小心tails中的位置会被后续元素不断替换回溯时必须从tails最后一个位置对应的下标开始并通过prev链回溯。我第一次实现这个方案时就是因为从tails的值而不是下标出发回溯导致输出的序列顺序不对。细节全是细节。5. 高频易错点与面试避坑指南5.1 六个必踩的坑列一下我实际做题和给别人讲题时见过的高频错误每一句都是踩出来的第一把dp[n-1]当成最终答案。dp[i]是以nums[i]结尾的 LIS全局答案要在所有dp[i]里取最大值。第二忽略n 0的边界。空数组返回 0这是最容易漏判的边界条件之一。第三初始值不设置成 1。dp数组的初始值应该是 1因为单个元素本身就是一个递增子序列。有的人初始化为 0导致后续转移全部少了 1。第四bisect_left和bisect_right用混。严格递增用bisect_left非递减用bisect_right这是死规律没有例外。第五更新dp[i]时忘记加 1。转移方程是dp[j] 1不是dp[j]这个低级错误很多新手会犯。第六在循环里把nums[j] nums[i]写成nums[j] nums[i]。如果是严格递增题目相等的值是不能组成子序列的写错就导致结果偏大。5.2 面试时的思路表达模板面试中如果遇到 LIS推荐按这样的节奏来回答先给出暴力递归思路说明问题规模不允许枚举。然后给出dp[i]的状态定义和转移方程解释为什么“以 i 结尾”这个定义能解决重叠子问题。接着手写 O(n^2) 代码在纸上演示一个简单例子的dp数组变化过程。如果面试官追问“能不能更快”再引出tails数组和二分优化并且主动说明“用bisect_left保证严格递增的替换语义”。最后可以主动提一下“这个题的变体包括非递减和二维排序”展现你对问题边界的理解。这个方法非常有效因为面试官想看到的不是你会不会这道题而是你有没有系统的解题思维。6. 实测数据与性能对比6.1 不同数据规模下的表现我在本机跑了三组典型数据规格是随机数组、元素范围与 n 成正比。对照组是朴素 DP 和二分优化记录耗时单位毫秒约取 5 次均值n朴素 DP O(n²)贪心二分 O(n log n)1000约 18ms约 0.4ms10000约 1850ms约 5ms100000约 180s跑不动了约 55ms可以看到n 10000 时两者差距已经超过 360 倍越到后面差距越恐怖。这组数据也印证了一个很朴素的道理同一个问题优化前后可能完全不在同一个量级竞争。6.2 关于记忆化搜索的一个补充有读者可能记得在刷题网站上见过用functools.lru_cache的递归方案那个方案在 Python 里确实能跑过许多中等数据但它有几个隐患递归深度受限制sys.setrecursionlimit改多了容易爆栈缓存键是下标但如果你用“当前下标 上一个值”作为一个 pair 来定义状态状态数还会膨胀。对于 LIS 来说dp[i]的定义只需要下标没必要加“上一个值”作为状态维度这也是“以 i 结尾”这个定义天然的优势所在。7. 复盘与几个实用心得LIS 这道题我已经写过很多遍每次写还是有新的体会。这里分享几个纯个人向的心得算不上教程但可能对正在刷题的人有点帮助。第一学动态规划不要在“看得懂题解”和“自己能推出来”之间画等号。我见过很多同学能默写出 LIS 的转移方程但问他“如果数组元素改成负数怎么办”他会愣住。实际上负数不影响任何算法逻辑但这一问就能把“背题”和“理解”区分开来。建议你合上代码拿一张空白纸自己从暴力递归开始推导一遍再写 DP再写二分。这个过程走完你才算真正掌握了这道题。第二对于 O(n²) 和 O(n log n) 这两种解法我的建议是“都会写优先写二分”。面试时 O(n²) 写起来快思路表达更直观但如果你能稳住直接写出二分说明你理解得足够透彻。实际我在面试中通常会先说 O(n²) 再说优化因为这样能展示你的思维演进过程。第三LIS 的套路可以迁移到很多看似无关的问题上。比如最长递增路径、最小删除次数使数组有序、二维套娃信封本质都是同一个核心。刷透一道经典题的价值远大于泛泛刷十道简单题。第四也是最重要的一点不要只看代码长度来判断算法难度。二分的代码只有十行但背后有正确的贪心证明、有序性维护、相等值处理三个层次的理解。如果你读到这里能把这三层用自己的话讲清楚那你对 LIS 的掌握已经超过了绝大多数只背模板的人。最后再分享一个小技巧如果你在用 Python 刷题优先用bisect模块而不是手写二分。它的 C 底层实现速度更快而且bisect_left和bisect_right的语义非常标准不容易写错。等你在刷题网站上用熟了这两个函数连tail的维护都可以写得更顺手。 
长河君 · 2026/10/15 17:01:39 · 阅读 1.2k 最长递增子序列详解：从朴素DP到贪心+二分的优化之路
最近在系统过动态规划专题刷到最长递增子序列Longest Increasing Subsequence简称 LIS这道题时我特意停下来多花了些时间。倒不是因为它难恰恰相反它是动态规划里非常适合用来理解“状态设计”和“优化方向”的入门经典。网上的题解很多但大部分只是给出转移方程和代码少有讲清楚“为什么这么设计状态”“为什么二分优化是对”的。这篇文章我把自己的完整思考过程记录下来包括朴素 DP 的推导、二分的优化思路、正确性证明、常见变体以及我在实际做题中踩过的几个有意思的坑。如果你正在准备算法面试或者刚开始接触动态规划这篇文章应该能帮你把这道题吃透。1. 问题定位与前置分析1.1 题目到底在问什么先看一个标准定义给定一个无序的整数数组找到其中最长的严格递增子序列的长度。注意几个关键词——“子序列”不是“子数组”它不要求元素在原数组中连续但元素的相对顺序不能改变。比如[1, 2, 3]是数组[3, 1, 2, 0, 3]的子序列而[3, 1]就不是因为它在原数组中是逆序的。另一个容易踩坑的关键词是“严格递增”。严格递增意味着nums[j] nums[i]而不是。如果题目改成“非递减”那在边界处理和二分查找的细节上会有一处关键差异后面我单独说。这个问题有意思的地方在于它表面上看起来像是一个“找最长”的暴力搜索问题但因为元素之间没有连续性限制子序列的数量是指数级的。拿一个长度为 n 的数组来说子序列总数是 2^n暴力枚举根本不现实。这就是我们需要动态规划或贪心加二分这类优化算法的根本原因。1.2 为什么动态规划能派上用场动态规划能解决的问题通常有两个关键特征重叠子问题和最优子结构。LIS 恰好两个都占。从最优子结构来看如果我们已经知道了nums[0..i]这个前缀的某个信息能否直接推导出nums[0..i1]的答案能但有个关键点——光是知道“前缀的最长递增子序列长度”是不够的。比如数组[4, 5, 1, 2]前缀[4, 5]的 LIS 长度是 2末尾元素是 5而前缀[4, 5, 1]的 LIS 长度仍然是 2但末尾元素变成了 1子序列是[4, 5]或[1]都可以。这时候如果给数组新增一个元素3最终 LIS 是[1, 2, 3]长度为 3。如果我们只记录“前缀 LIS 长度”这个信息就丢掉了一个关键信息不同长度的递增子序列的末尾元素最小值。所以状态设计的核心困境在于我们要在“记录什么”和“怎么转移”之间找到一个合适的平衡。不同的问题有不同的解法LIS 的经典做法是固定“以某个元素作为子序列的结尾”。1.3 从暴力搜索到记忆化搜索很多人一上来就看 DP 解法我可以理解但如果你从来没自己推过暴力搜索直接看转移方程多少有点悬空。把暴力递归写出来你才能直观感受什么叫“重叠子问题”。暴力思路很简单从每个位置出发尝试它后面所有比它大的元素递归找最长。用递归函数f(i)表示“以nums[i]作为子序列最后一个元素的最长递增子序列长度”那么def dfs(nums, i): res 1 for j in range(i 1, len(nums)): if nums[j] nums[i]: res max(res, 1 dfs(nums, j)) return res这个写法的时间复杂度是 O(2^n)因为每个元素都有“选”和“不选”两条路。但仔细观察会发现很多子问题是重复的——例如dfs(5)可能在多个递归分支里都被反复计算。用一个数组把dfs(i)的结果存起来就是记忆化搜索时间降到 O(n^2)。不过记忆化搜索本质还是递归有栈溢出风险而且代码也比迭代麻烦。在实际刷题中我更喜欢直接写迭代 DP但理解记忆化搜索能帮你确认“状态定义是自洽的”。这也是我把暴力方案写出来的原因。2. 朴素动态规划O(n²) 解法详解2.1 状态定义与转移方程现在直接给出经典解法。定义dp[i]为“以nums[i]结尾的最长递增子序列的长度”。注意这个限定——“以nums[i]结尾”这是整个状态设计的灵魂。为什么要这么定义因为我们面对的是一个无序数组不能像连续子数组那样直接比较相邻两个位置。但如果我们把视角固定在“当前元素作为子序列的最后一个元素”上那么前面只需要考虑那些值比它小的元素即可。这样转移关系就清晰了dp[i] max(1, max(dp[j] 1 for j i if nums[j] nums[i]))1是保底值因为单个元素本身就是一个长度为 1 的递增子序列。如果前面没有任何元素比nums[i]小那dp[i]就只能等于 1。这里我特别想强调一个初学者容易踩的坑dp[i]并不是“数组前 i 个元素中 LIS 的长度”而是“以第 i 个元素结尾的 LIS 长度”。这两个定义看着很像实际差别巨大。如果把dp[i]当成“前 i 个元素的最优解”你会在转移时试图跨过元素任意组合方程就写不出来就算硬写也会丢掉“递增”这个顺序约束。正确答案是dp[i]算完之后整个数组的 LIS 长度是max(dp[0..n-1])而不是dp[n-1]。这个误区几乎是每个初学者都踩过的我当年也不例外总是下意识以为最后一个状态就是全局最优实际上 LIS 的最长子序列不一定包含最后一个元素。比如数组[10, 9, 2, 5, 3, 7, 101, 18]最长子序列是[2, 3, 7, 101]或者[2, 5, 7, 101]末尾元素是101而不是18所以答案在dp[6]而不是dp[7]。2.2 核心代码实现与时空复杂度用 Python 写朴素 DP 非常简洁def length_of_lis(nums): n len(nums) if n 0: return 0 dp [1] * n for i in range(1, n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)内层循环要扫描i之前的所有元素所以总时间是1 2 ... n - 1也就是 O(n^2)。空间只用了一个长度为 n 的dp数组O(n)。如果你需要同时输出最长递增子序列本身而不仅仅是长度可以在每次更新dp[i]时记录一个prev[i]数组存下“上一个元素的下标”。最后从dp值最大的那个下标开始沿着prev往前回溯就能还原出具体的子序列。不过要注意这样还原出来的只是“某一个”最长递增子序列不是唯一的。在实际面试中面试官更常问的是“能否用二分优化到 O(n log n)”这就是下一节的内容。2.3 朴素 DP 的局限与优化动机O(n^2) 在 n 较小时完全够用比如 n 1000 时就是一百万次操作。但很多在线测评系统的数据范围是 n 10^5 甚至 10^6O(n^2) 就会超时。面试中如果候选人能主动提出“这个问题可以用贪心加二分优化到 O(n log n)”会是一个很加分的信号。但我要提醒一点不要因为学会了二分优化就完全轻视朴素 DP。二分优化的代码更短但理解门槛更高朴素 DP 虽然慢但它的状态转移关系更加直观。从学习路径来看先完全理解朴素 DP再理解优化方案才是合理的顺序。我自己在给同学讲这道题时发现一个有趣的现象直接看二分优化的解法很多人能背下代码但问他“为什么二分能保证正确”就答不上来。这说明没有建立起从朴素到优化的思维演化路径。3. 贪心 二分O(n log n) 优化方案3.1 核心思想保存“最有潜力的子序列”优化的关键思路是我们维护一个数组tails其中tails[k]表示“长度为 k1 的递增子序列中最小的末尾元素值”。注意这里说的是“最小的末尾元素值”而不是“某个具体的子序列”。为什么只关心末尾元素的最小值因为对于同样长度的递增子序列末尾元素越小后面就越容易接上更大的元素这个子序列的“扩展潜力”就越大。举个例子数组[2, 3]和[1, 3]都是长度 2 的递增子序列假设后面要接4两者都能接但如果后面是2那么只有[1, 2]能续上[2, 3]不行。所以对于长度相同的子序列末尾值越小的越值得保留。这本质上是一种贪心策略我们要维护的是“最优的”长度为 k 的子序列贪心在末尾元素上做了选择把更大的末尾值丢弃。这种做法的正确性需要严格证明但直觉上非常合理。用一句大白话总结相同长度尾巴越小越有前途。3.2 tails 数组与二分查找的配合现在的问题是如何高效维护tails数组当扫描到一个新元素x时我们要在tails中找一个合适的位置。具体规则是如果x比tails中所有元素都大说明x可以接在目前最长子序列的后面形成一个更长的子序列所以把x追加到tails末尾。否则在tails中找到第一个大于等于x的元并替换它。这一步利用了一个重要的性质tails数组本身就是严格递增的所以可以用二分查找。这段描述是网上最常见的解释但只说“找到并替换”是不够的如果没有解释“为什么可以替换”你就没有真正掌握它。替换的本质是用x作为新的末尾元素代表一个“更有潜力”的同长度子序列。而这个替换不会破坏tails的有序性因为x肯定小于被替换的那个元素且大于等于它前面的元素这是二分查找保证的。所以tails始终是有序的也就能继续二分。用生活化的类比来解释比如你是教练要组建一支递增序列的“队伍”tails[k]记录的是“第 k 个位置的队员里最矮的那一个”。如果有新人来他比当前队伍里的某个人矮但又不是太矮就让他顶替那个身高相近的队员。队伍长度没有立刻变长但队伍的整体平均身高拉低了未来更容易吸收高个子队员。这就是为什么二分法能找到问题的最优解——我们一直在用“更小末尾”换掉“较大末尾”而不改变队伍长度。3.3 标准代码与正确性论证下面是 Python 实现import bisect def length_of_lis(nums): tails [] for x in nums: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)bisect_left是关键。它的语义是在tails中找到第一个大于等于x的位置。对于严格递增子序列遇到一个与x相等的元素时不需要替换它因为“同值替换”对后续没有帮助反而可能破坏严格递增的语义。这段代码为什么是正确的我们需要从两个层面来论证第一tails的长度等于当前已经找到的最长递增子序列长度。这一点可以通过数学归纳法证明初始tails为空长度为 0每次如果x大于tails中所有元素长度加 1否则长度不变但某个位置的值变小。长度变化的时机对应着真正孕育出了更长子序列。第二tails数组严格递增。这一点通过bisect_left的定位规则来保证替换位置pos满足tails[pos-1] x tails[pos]边界条件除外替换后有序性依然成立。再加上多加的每轮判断tails的整体严格递增性质不会破坏。这两点证明不算复杂但第一次看到时很容易忽略它们。尤其是第二点如果新手用的是bisect_right或者没有考虑x与已有元素相等的情况很可能会得到错误的答案。所以我把代码里的bisect_left单独拎出来强调一下这是细节所在。3.4 为什么二分法返回的是长度而不是具体子序列很多人在学习这个优化时会产生一个疑问tails最终的内容并不是某个真正的递增子序列那答案长度还可靠吗问得好。tails数组的每一个位置确实都来自某个子序列的末尾元素但这些元素拼在一起并不一定构成一个合法子序列它们分属不同的“候选序列”。比如数组[3, 1, 2]最终tails [1, 2]这恰好是一个合法子序列但换个例子[2, 1, 3]最终tails [1, 3]虽然[1, 3]在原数组里它也是合法的1 在 3 前面但更复杂的情况下tails的某些值来自不同的分支。比如[1, 3, 0, 2, 4]最终tails [0, 2, 4]这个序列在原数组中并不存在0 在 2 后面不在前面。因此tails不是真正的答案序列它只是一个“状态记录器”。我们只信任它的长度不信任里面的具体值。如果你需要还原出真正的递增子序列最稳妥的办法是回到朴素 DP 加上prev指针或者用另一种“耐心排序”变体来记录每个位置对应的原数组下标和前缀信息。不过在绝大多数只需要长度的场景里tails方案已经足够。4. 变体问题与实战进阶4.1 最长非递减子序列面试和竞赛中一个最常见的变体是把“严格递增”改成“非递减”。此时相邻相等是允许的所以状态转移条件从nums[j] nums[i]变成nums[j] nums[i]。对应的二分优化也要改一行bisect_left改为bisect_right。为什么因为对于严格递增新来的x如果与tails[pos]相等替换它是没有意义的严格递增不允许相等但对于非递减相等的值可以接在已有序列后面所以新来的相等元素应该被追加到“相同值的后面”这样才能扩展长度。这个细节是面试官非常喜欢挖的考点。如果你能直接说出这个区别对方就知道你真的理解了这个算法而不只是背了代码。4.2 二维变体俄罗斯套娃信封问题我最初完全没有意识到 LIS 的扩展空间这么大直到碰到“俄罗斯套娃信封问题”。题目要求你求最多能套多少层信封每个信封有宽度和高度套娃的条件是宽度和高度都严格大于内层信封。解法是先按宽度升序排序宽度相同时按高度降序排序。然后对高度数组求 LIS。这里的高度降序是一个精妙的设计宽度相同的信封不能互相套入按降序排列可以让这些信封在求 LIS 时天然不可互选因为后序信封的高度都小于或等于前序不会被选入递增序列。这类“排序 LIS”的组合技巧是动态规划进阶的常见套路。4.3 LIS 在工程中的现实场景有人可能会问这道题除了面试实际工程里有价值吗答案是有的。一个典型的应用是“最小插入次数让数组有序”。给定一个几乎有序的数组我们希望尽可能少地移动元素使其变成严格递增。那么只需要找到原数组中的 LIS其他元素就是需要移动的。这个思路在一些数据处理管道里的有序性修复、增量排序策略中很常见。另一个场景是基因序列分析。在生物信息学中比较两条 DNA 序列的相似度时本质上是找它们的“最长公共子序列”LCS而 LCS 可以规约到 LIS 问题。如果你对算法竞赛比较熟悉应该知道“最长公共子序列转 LIS”这个经典技巧——通过将其中一个序列的每个元素映射到它在另一个序列中的位置按降序排列以避免选中多个相同元素就转换成了 LIS 问题。4.4 输出具体子序列的两种方案说了这么多可能有人已经发现一个问题二分优化只给长度不给子序列本身。如果题目既要求长度又要求打印具体序列该怎么办方案一用朴素 DP 加入prev数组O(n^2) 时间换取完整路径。适合 n 较小的情况。方案二在二分优化的基础上额外维护一个pos_idx数组记录每个tails位置对应的原数组下标同时维护prev数组记录每个下标的“前驱下标”。这样在遍历完所有元素后可以回溯得到完整子序列。这种方案的时间复杂度仍然是 O(n log n)但要小心tails中的位置会被后续元素不断替换回溯时必须从tails最后一个位置对应的下标开始并通过prev链回溯。我第一次实现这个方案时就是因为从tails的值而不是下标出发回溯导致输出的序列顺序不对。细节全是细节。5. 高频易错点与面试避坑指南5.1 六个必踩的坑列一下我实际做题和给别人讲题时见过的高频错误每一句都是踩出来的第一把dp[n-1]当成最终答案。dp[i]是以nums[i]结尾的 LIS全局答案要在所有dp[i]里取最大值。第二忽略n 0的边界。空数组返回 0这是最容易漏判的边界条件之一。第三初始值不设置成 1。dp数组的初始值应该是 1因为单个元素本身就是一个递增子序列。有的人初始化为 0导致后续转移全部少了 1。第四bisect_left和bisect_right用混。严格递增用bisect_left非递减用bisect_right这是死规律没有例外。第五更新dp[i]时忘记加 1。转移方程是dp[j] 1不是dp[j]这个低级错误很多新手会犯。第六在循环里把nums[j] nums[i]写成nums[j] nums[i]。如果是严格递增题目相等的值是不能组成子序列的写错就导致结果偏大。5.2 面试时的思路表达模板面试中如果遇到 LIS推荐按这样的节奏来回答先给出暴力递归思路说明问题规模不允许枚举。然后给出dp[i]的状态定义和转移方程解释为什么“以 i 结尾”这个定义能解决重叠子问题。接着手写 O(n^2) 代码在纸上演示一个简单例子的dp数组变化过程。如果面试官追问“能不能更快”再引出tails数组和二分优化并且主动说明“用bisect_left保证严格递增的替换语义”。最后可以主动提一下“这个题的变体包括非递减和二维排序”展现你对问题边界的理解。这个方法非常有效因为面试官想看到的不是你会不会这道题而是你有没有系统的解题思维。6. 实测数据与性能对比6.1 不同数据规模下的表现我在本机跑了三组典型数据规格是随机数组、元素范围与 n 成正比。对照组是朴素 DP 和二分优化记录耗时单位毫秒约取 5 次均值n朴素 DP O(n²)贪心二分 O(n log n)1000约 18ms约 0.4ms10000约 1850ms约 5ms100000约 180s跑不动了约 55ms可以看到n 10000 时两者差距已经超过 360 倍越到后面差距越恐怖。这组数据也印证了一个很朴素的道理同一个问题优化前后可能完全不在同一个量级竞争。6.2 关于记忆化搜索的一个补充有读者可能记得在刷题网站上见过用functools.lru_cache的递归方案那个方案在 Python 里确实能跑过许多中等数据但它有几个隐患递归深度受限制sys.setrecursionlimit改多了容易爆栈缓存键是下标但如果你用“当前下标 上一个值”作为一个 pair 来定义状态状态数还会膨胀。对于 LIS 来说dp[i]的定义只需要下标没必要加“上一个值”作为状态维度这也是“以 i 结尾”这个定义天然的优势所在。7. 复盘与几个实用心得LIS 这道题我已经写过很多遍每次写还是有新的体会。这里分享几个纯个人向的心得算不上教程但可能对正在刷题的人有点帮助。第一学动态规划不要在“看得懂题解”和“自己能推出来”之间画等号。我见过很多同学能默写出 LIS 的转移方程但问他“如果数组元素改成负数怎么办”他会愣住。实际上负数不影响任何算法逻辑但这一问就能把“背题”和“理解”区分开来。建议你合上代码拿一张空白纸自己从暴力递归开始推导一遍再写 DP再写二分。这个过程走完你才算真正掌握了这道题。第二对于 O(n²) 和 O(n log n) 这两种解法我的建议是“都会写优先写二分”。面试时 O(n²) 写起来快思路表达更直观但如果你能稳住直接写出二分说明你理解得足够透彻。实际我在面试中通常会先说 O(n²) 再说优化因为这样能展示你的思维演进过程。第三LIS 的套路可以迁移到很多看似无关的问题上。比如最长递增路径、最小删除次数使数组有序、二维套娃信封本质都是同一个核心。刷透一道经典题的价值远大于泛泛刷十道简单题。第四也是最重要的一点不要只看代码长度来判断算法难度。二分的代码只有十行但背后有正确的贪心证明、有序性维护、相等值处理三个层次的理解。如果你读到这里能把这三层用自己的话讲清楚那你对 LIS 的掌握已经超过了绝大多数只背模板的人。最后再分享一个小技巧如果你在用 Python 刷题优先用bisect模块而不是手写二分。它的 C 底层实现速度更快而且bisect_left和bisect_right的语义非常标准不容易写错。等你在刷题网站上用熟了这两个函数连tail的维护都可以写得更顺手。