1. 为什么LIS这道题值得单独拿出来研究最长递增子序列Longest Increasing Subsequence通常简称LIS是算法题里的常客LeetCode上有专门题号面试里出现过无数回。但这道题真正有意思的地方不是“动态规划”这个标签而是它背后横跨了DP、二分查找、贪心三大基础算法一个问题的解串起了整个算法知识体系。我见过不少开发者在这道题上栽过跟头有人背住了O(n^2)的DP模板就以为通关了结果面试官一句“能不能优化到O(n log n)”就哑火。也有人写对了二分优化的代码但讲不清tails数组为什么能二分最后被深挖一步就露馅。这道题的价值正在于此——它能精准筛出“会背模板”和“真懂算法”的人。先说清楚概念。子序列subsequence和子串substring一字之差性质完全不一样。子串必须连续比如数组中一段挨在一起的元素子序列不要求连续只要保持相对顺序就行。比如数组[2, 5, 1, 3, 4, 8][2, 4, 8]是子序列但不是子串因为它跳过了5和1。最长递增子序列的意思就是在这些不连续的子序列里找到长度最长、且元素严格递增的那一条。很多人第一反应是“这有什么难的一层层找呗”但真到实现层面就发现问题了你没法确定当前选的元素到底应不应该保留——选了它可能得到更长序列也可能挡了后面更大的元素的路。这种“局部选择影响全局结果”的特征决定了它没法用一把梭的贪心直接解决虽然优化版本里确实有贪心的影子后面细说。另一个让它值得研究的原因是应用面特别广。从工程角度文本diff的Myers算法、视频编码的参考帧选择、依赖关系的拓扑约减甚至是股票买卖策略的变体题背后都藏着LIS的影子。可以说搞懂LIS一道题等于顺手摸清了一整类序列优化问题的思路。这篇文章我就按自己学习时的实际路径来写先讲最直观的DP做法再拆解O(n log n)优化的完整原理然后掰开揉碎说清楚tails数组的二分查找为什么成立最后聊几个实战中反复出现的变体和坑。读完之后你不仅能写对代码还能在面对“为什么这样对”的追问时对答如流。2. 最朴素的O(n²)解法状态怎么想才是关键2.1 状态定义为什么必须落在“以i结尾”拿到底一道DP题最头疼的就是状态定义。我第一次做LIS时第一反应是定义dp[i]为“前i个元素里的最长递增子序列长度”——然后很快就发现这个定义有致命问题光知道前i个元素里的最长长度你根本不知道这个序列是哪个元素结尾的也就判断不了下一个新元素能不能接上去。正确做法是把状态定义为dp[i]表示以nums[i]作为结尾元素的最长递增子序列长度。这个“必须包含nums[i]”的约束看着不起眼实际是整个转移能成立的基础。因为你知道了以nums[i]结尾的序列长度下一个元素nums[j]j i想接上去只需要判断nums[j]是否大于nums[i]就行。用生活化的类比这就像接力赛dp[i]记录的是“第i棒选手作为最后一棒最长能跑多远”。要知道下一棒选手能不能接到他手里只看两件事——上一棒是谁因为要数值递增以及这位选手当前能带多远。2.2 转移方程推导与一个完整手算例子转移逻辑其实就一句话dp[i] max(dp[j] 1)其中所有j i且nums[j] nums[i]。所有满足“能在nums[i]前面接上”的位置里挑出带来最长结果的加上nums[i]自己延长出来的1。初始值dp[i] 1因为单个元素本身就是一个长度为1的递增子序列。光看公式容易飘我拿一个具体数组完整走一遍nums [10, 9, 2, 5, 3, 7, 101, 18]。我们逐个求dp索引元素能接的位置候选dp值dp[i]010无开头1119无1122无1135索引2值2dp[2]12243索引2值2dp[2]12257索引2值2、索引3值5、索引4值3dp[4]1336101所有比它小的最大是dp[5]1444718索引5值7最好dp[5]144答案是整个dp数组的最大值4对应子序列[2, 5, 7, 101]或者[2, 3, 7, 18]长度一样但实际内容不同。这一步很重要LIS长度是唯一的但LIS本身可能不唯一。这里有个新手容易踩的误区最后答案是max(dp)不是dp[n-1]。因为最长递增序列不一定非要把最后一个元素包含进去以哪个元素结尾都可能达到最优。我一同学就是这里翻车的测试用例里刚好最长序列以末尾元素结尾时通过了换一个数据就错。2.3 O(n²)解法的工程适用面这个解法的代码实现很直接外层循环遍历所有位置i内层循环遍历所有j i总时间O(n²)空间O(n)只存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)但说实话O(n²)这个复杂度在真实工程里并不够用。我曾处理过一个上万长度的序列O(n²)跑了将近一分钟而后面讲的O(n log n)版本毫秒级出结果。所以面试里如果你只交出O(n²)大概率会面临“还能优化吗”的追问——这就到了这篇文章的动真格部分。3. O(n log n)优化的核心洞察tails数组到底在维护什么3.1 从“以i结尾”到“长度为k的最小末尾”优化思路不直接改DP方程而是换一个视角看问题。我们不再关心“以每个元素结尾的LIS长度”而是反过来维护一个数组tails[k]表示长度为k1的递增子序列中最小的末尾元素值。这个定义初看很抽象我解释一下就通了。假设目前找到了长度为3的递增子序列可能有多种组合末尾值可能是5也可能是8。这时候tails[2]就存5因为长度为3的序列我们只关心最小的末尾是多少。为什么要最小因为末尾越小后面新元素越容易接上去这个“保留最优候选”的思想就是贪心所在。有个非常直观的类比找LIS就像在一排牌桌上按顺序整理扑克牌每张新牌来了我们把它放到“最合适”的那堆牌上规则是放到所有堆顶牌中第一张不小于它的牌上如果没有就新开一堆。最后牌堆数就是LIS长度。这个玩法叫Patience Sorting耐心排序tails数组对应的就是每堆牌最上面的那张牌。3.2 维护过程拆解替换还是追加tails数组的维护逻辑分为两种情况。对每个新元素xx大于tails所有元素说明找到了更长的递增子序列把x追加到tails末尾LIS长度加1。x不大于tails最大元素在tails中二分查找第一个不小于x的位置用x替换它。替换这个动作是唯一看起来反常的地方。用前一个数组[10, 9, 2, 5, 3, 7, 101, 18]试一遍10 → tails [10]9 → 二分找到位置0替换 → tails [9]2 → 替换位置0 → tails [2]5 → 大于2追加 → tails [2, 5]3 → 二分找到位置1第一个不小于3的是5替换 → tails [2, 3]7 → 大于3追加 → tails [2, 3, 7]101 → 追加 → tails [2, 3, 7, 101]18 → 二分找到位置3第一个不小于18的是101替换 → tails [2, 3, 7, 18]最终tails长度是4与真值一致。仔细看tails数组本身始终严格递增——这正是它能用二分查找的前提条件。3.3 为什么替换不会破坏正确解这是核心中的核心面试官最爱深挖的地方。很多人不理解在第5步把tails[1]从5替换成3时等于丢弃了子序列[2, 5]这个操作会不会导致最终答案丢失答案是不会原因需要看清楚一点tails[k]的含义从来不是“一个确定的、唯一的长度为k1的序列”而是“长度为k1的所有递增子序列中末尾能取得的最小值”。5和3代表长度2的序列有两种可能3更好因为更小。而且替换这个动作不影响已经达到的长度——tails长度没变只是把该长度的“底线”压得更低让后续元素更容易构建更长的序列。证明可以这样想如果长度k存在某个末尾值为v的递增子序列那么tails[k-1]一定小于v因为子序列内部递增倒数第二个元素必然小于v。这保证了tails的严格递增结构。替换时我们找到的是第一个不小于x的位置p说明tails[p-1] x于是可以用tails[p-1]那个序列接上x得到长度p1、末尾为x的合法递增子序列且x小于原来tails[p]的值——所以这是一个长度不变、末尾更优的替代品。数学归纳法一路推下来最终答案一定正确。3.4 二分边界与代码实现的微妙之处到代码层面核心就是二分查找的边界写对。我给出一个我实际验证过的版本import bisect def length_of_lis(nums): tails [] for x in nums: i bisect.bisect_left(tails, x) if i len(tails): tails.append(x) else: tails[i] x return len(tails)这里Python标准库的bisect_left直接帮我们完成了“第一个不小于x的位置”的查找。如果用C对应的就是lower_bound。但这里有个极其隐蔽的坑必须用bisect_left不能用bisect_right。这个问题在刷题群里争论过很多回。差别在于重复元素。如果数组是[2, 2]严格递增要求下第二个2不能接在第一个2后面所以第二个2应该走“替换”分支用bisect_left得到位置0替换tails长度保持1正确答案是1。如果用bisect_right它会找到末尾位置1因为相等元素按“大于”处理长度错误变成2。这也印证了LIS题设的“递增”默认是严格递增等于的情况一律走替换。4. 从刷题到工程LIS真实落地的地方4.1 文本diff算法里的LIS影子很多开发者第一次接触LIS是在力扣上觉得这只是面试题和日常工作没什么关系。我第一次感觉到“这题真有用”是在研究文本diff工具原理的时候。经典的diff本质是求解两个文本的最长公共子序列LCS——公共的部分尽量不动只对差异部分做增删。而LCS问题可以通过一个巧妙的转换变成LIS问题把第一个序列的元素映射到它在第二个序列中出现位置的数组然后求这个位置数组的最长递增子序列。公共子序列越长diff出来修改的地方就越少我们平常看到git diff里那几行精简的改动底层就有这个思路的影子。我当时所在的项目组做过一个配置文件的版本比对工具数据量不大用动态规划求LCS就够了。但如果比对的是大日志文件或代码仓库快照O(n*m)的DP就扛不住了优化路径就会走向LIS的O(n log n)方案。理解这层关联之后你在做任何“求两串数据相似度”的需求时思路会宽很多。4.2 二维LIS套娃信封问题的进阶玩法LIS最常见的变形之一是力扣上的“俄罗斯套娃信封”问题。信封有宽和高两个维度一个信封能装进另一个要求宽和高都比对方大问最多能套多少层。这题的正确姿势是把宽度从小到大排序、宽度相同则高度从大到小排序然后对高度序列求LIS。这里排序是关键宽度升序保证“后面信封宽度不小于前面”高度降序保证宽度相同时不会出现高信封装矮信封的非法情况因为高度降序它们之间不可能形成递增。对高度求LIS就自然过滤掉了宽度相等导致的误套。我做这道题时切身吃过排序列的亏。一开始只按宽度升序排相同宽度高度也升序结果高度序列中出现[5, 5]这种情况LIS会把它们算成有效递增实际宽度相同根本不满足条件。害得我调了半天后来突然想明白——相同宽度内高度降序让相等宽度的高度在求LIS时“互相干扰”从而自动剔除这才算是真正理解了这题的巧妙设计。这个变体的意义在于展示LIS如何从一维问题升维到二维。很多二维优化问题本质都是“先排序一个维度剩下的维度上跑一维算法”后续遇到类似的贪心结合排序的题目这个思路可以反复复用。4.3 依赖排序与数据归约工程里低配版的LIS除了这些教科书级的应用LIS思路在日常工程中还常以“低配版”形式出现。比如我曾在处理一批带时间戳的事件日志时要剔除掉一部分冗余记录让剩下的事件保持严格递增的时间顺序且数量最多——这本质上就是LIS。再比如视频编码里选择参考帧某些场景下需要选出尽可能多且帧序递增的关键帧用于预解码同样可以归约成LIS。这提醒我们一件事算法题不是孤立的脑力体操它解决的问题原型在真实系统里会以各种面貌出现。学LIS时脑子里多挂一个“序列中尽量多地保留递增关系的元素”的钩子比单纯记模板有用得多。5. 刷题面试里反复出现的坑我都替你踩过了5.1 “非递减”和“严格递增”的送命题这是LIS题面上最容易看漏的条件。力扣原题是“严格递增”也就是nums[j]必须严格小于nums[i]等号都不行。但对“最长非递减子序列”Longest Non-Decreasing Subsequence等号就合法了。两者在代码上的差别就一处二分查找用bisect_left还是bisect_right。严格递增对应bisect_left找第一个x的位置非递减对应bisect_right找第一个x的位置相等时不替换而是追加或前推。这个细节曾经在某次面试里直接让面试官问了十五分钟——他把题目改成“非递减”后看我会不会切换二分策略。有个取巧的记忆方式tails数组里不能出现相同元素。严格递增版本用bisect_left保证相等时替换tails中就不会有两个一样的值非递减版本用bisect_right保证相等时跳过或追加tails中可以出现相等值。反过来想也就知道该选哪个了。5.2 只求长度和要还原序列的区别如果题目只问LIS长度二分优化的代码已经够用。但如果要你输出完整的最长递增子序列事情就多了两步。第一你需要在dp被更新时记录每个位置的前驱节点然后从长度最大的位置回溯。第二二分优化版本维护的tails数组不能直接当作结果序列输出。这一点很多人都懵过tails最终是[2, 3, 7, 18]但实际LIS可能是[2, 5, 7, 101]两者长度一致但内容完全不同。因为tails数组中替换操作只保证“存在某种长度的序列末尾能取到这个值”并不保证这个替换后的元素真的出现在最终最优序列里。要还原真正的序列通常还是在O(n log n)过程中额外记录每个元素被加入到tails时所处的长度再辅以二分定位的过程反向追溯。面试时如果被要求输出序列建议先问清楚是否只要长度否则很容易在还原上浪费大量时间。5.3 空数组和极端大小的边界处理边界问题看着低级但真能坑人。空数组越界不用说直接返回0即可。单元素数组返回1。全递减数组返回1。全相等数组严格递增定义下返回1而“非递减”版本返回n。还有一类隐藏坑元素过大比如1e9这种如果用哈希表或记录路径的变种容易开过大数组造成内存溢出。二分解法只存储tails长度和n同阶内存O(n)基本没有危险。我见过有人在O(n²)解法基础上强行优化导致内存爆掉的例子所以如果数组规模过万优先考虑二分解法。5.4 “长度最大”和“和最大”分不清LIS还有个经典变种叫“最大和递增子序列”同样是递增但目标函数从“长度最大”变成“元素之和最大”。很多初学者想当然把LIS的tails策略搬过去结果发现求和场景下“末尾最小”的贪心完全失效——因为末尾小的序列虽然容易延长但累计和可能很小甚至不如一个末尾大但总和大的序列。这时状态定义就回到经典的dp[i] nums[i] max(dp[j])nums[j] nums[i]O(n²)解法是正解不再有O(n log n)的简单二分优化严格说可以用线段树或树状数组优化到O(n log n)但这是另一套知识了。这个对比很有价值它提醒我们贪心策略依赖于目标函数的单调性换了目标函数就必须重新审视优化手段是否仍然成立。6. 从这道题带走的思考方式我学习LIS的过程大致经历了三个阶段先是背O(n²)模板然后理解DP状态为什么那样定义最后才想通二分优化那个“替换”操作为什么不影响正确性。第三个阶段是最难的也是收获最大的。有个很笨但有效的方法把tails数组的每一步演变亲手画出来。不要只在脑子里推拿笔在纸上把每次替换前后tails的内容写下来标出当前元素、找到的位置、替换前后的值。画过三个测试用例之后你自然会理解tails的意义。我也推荐初学者自己动手实现一遍二分查找不用语言自带的库函数用left和right指针一步步走这样对“第一个不小于x”这个边界条件的感受会比直接调库深得多。至于面试中聊到这道题我的经验是先讲清楚子序列和子串的区别然后给出O(n²)的DP状态定义和转移方程这时候主动提出“还可以优化到O(n log n)”并解释tails数组的含义最后在二分查找时顺势点明严格递增要用bisect_left。每一步都说出“为什么”而不只是“是什么”这才是这道题真正想考察的东西——不是你会背代码而是你是否理解算法决策背后的权衡。最后再分享一个做题习惯。每次遇到新题我都先问自己三个问题目标函数是什么状态需要记录哪些信息能不能用贪心简化LIS这道题把三个问题都占了目标函数是长度状态必须记录末尾元素才能转移二分优化说明贪心能奏效。能把这套思考框架迁移到其他题上刷题才不会变成海量背题。
看内容编号体系：设计逻辑与实操方法)