全解：从O(n²)动态规划到贪心二分优化与路径还原)
最长递增子序列圈内都叫它LIS全称Longest Increasing Subsequence。这名字看着学术其实特别接地气——就是给你一个乱序数组让你在里面挑一些数出来保持相对顺序不变组成一个严格递增的序列问这个序列最长能有多长。就这么个问题从大一数据结构课到大厂面试手撕代码再到蓝桥杯、ACM区域赛到处都是它的影子。今天我把这东西彻底讲透从朴素的动态规划到能跑百万级数据的贪心二分模板再附上我这些年刷题攒下来的变体题单和解法要点一篇文给你安排明白。这篇东西适合谁看刚学DP的大一选手面试前突击算法的求职党还有刷LeetCode和竞赛题卡在LIS变体上的老手。看完你能收获三样东西一套不会写错的O(n log n)模板一份覆盖各种花式考法的题集拆解以及一堆别人博客里不常写的坑和心得。1. LIS问题的本质与适用场景判断先把这个问题的本质聊清楚。LIS不是一个孤立的“背模板题”它背后是动态规划里极有代表性的一类模型——以某个位置结尾的最优子结构。你在纸上随便写一串数比如[3, 1, 2, 1, 8, 5, 6]肉眼扫一遍能看出最长上升子序列是[1, 2, 5, 6]或者[1, 2, 1, 5, 6]不对[1, 2, 1]中间那个1就断了严格递增不能相等。所以答案是[1, 2, 5, 6]或者[1, 2, 8]后者长度3前者长度4答案长度就是4。这个例子里藏了两个关键信息第一子序列不要求连续跳着选但顺序不能乱第二题目说的是“严格递增”也就是必须a[i] a[j]等于都不行。很多新手在这俩地方栽跟头——把“子序列”理解成“子数组”或者把“严格递增”直接放宽成“非递减”。这不是审题粗心的问题是你对模型的定义边界不清楚。后面讲变体的时候你会看到非严格递增的情况改一行代码就能处理但那是另一个问题不是LIS本身。判断一道题到底要不要用LIS模型我有个习惯先看数据规模。如果n在10^3级别O(n²)的DP可以过随便写。如果n到了10^5甚至10^6那基本就是在明着告诉你必须上O(n log n)的贪心二分做法。再看题意凡是“选出尽可能多的元素满足某种递增/偏序关系”的十有八九是LIS或者它的二维亲戚。比如套娃信封、最长数对链、合唱队形、删数使数组有序都能归到这一类。还有一个容易被忽略的判断维度问题要求返回什么。只问长度模板直接返回tail.size()轻松。要求输出具体序列就得额外维护一个pos数组做路径还原。要求统计方案数还得再维护一个计数数组。我见过不少人拿到“输出具体序列”就直接懵了因为平时只背了求长度的模板没看里层的原理。所以这篇文章后面会专门用一节讲路径还原这是从“会背模板”到“真正会做”的分水岭。2. 入门解法O(n²)动态规划2.1 状态设计与转移方程推导咱们先别急着上最优解法O(n²)的DP虽然慢但它是理解一切LIS变体的地基。而且小数据量下它写起来极其简单几乎不可能出错抢时间的时候反而好用。定义状态dp[i]表示“以第i个位置的数字作为结尾的最长递增子序列的长度”。注意是以a[i]结尾不是“前i个数字里能选出的最长长度”。这两个概念的区别很微妙但至关重要。以a[i]结尾意味着你选的这个子序列里最后一个元素必须是a[i]。这样定义的好处是转移的时候只用看前面的状态不用管后面的元素。转移方程长这样dp[i] max(dp[j] 1) 其中 0 ≤ j i 且 a[j] a[i]这句话翻译成人话就是我想知道以a[i]结尾能最长到多少就去前面遍历每一个a[j]如果a[j]比a[i]小满足递增条件那我可以把a[j]接在某个以a[j]结尾的递增子序列后面长度就是dp[j] 1。把所有满足条件的j都试一遍取最大值。如果前面一个满足条件的都没有dp[i]就保持初始值1——单个元素本身就是一个长度为1的递增子序列。这方程看着简单但我见过大量学生写错一个地方初始化。dp数组要全部初始化为1而不是0。原因就是上面说的任何单个元素自身构成长度为1的子序列。你要是初始化成0整个转移就全错了最后答案永远是0。2.2 代码实现与复杂度分析// O(n^2) LIS适合 n 1000 int lengthOfLIS(vectorint a) { int n a.size(); if (n 0) return 0; vectorint dp(n, 1); int ans 1; for (int i 0; i n; i) { for (int j 0; j i; j) { if (a[j] a[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; }这个写法里有两个容易翻车的细节。第一ans的更新要在内层循环结束之后用dp[i]去更新全局答案因为dp[i]可能比之前所有dp都大。第二内层循环遍历j的时候a[j] a[i]这个条件是严格小于不是小于等于。如果你处理的是非严格递增LIS这里就要改成a[j] a[i]。就这么一个符号的区别能让你在一道题上栽半个小时。复杂度很好算两层循环外层n次内层平均n/2次总的就是O(n²)空间O(n)。n1000的时候大概50万次运算眨眼功夫。但n10^5的时候是10^10次服务器都得卡几秒这时候就必须换更快的做法了。2.3 什么时候该用O(n²)而不是贪心二分很多人以为O(n log n)永远优于O(n²)所以直接背高级模板就完事了。但实际做题的时候我反而经常先写O(n²)。原因有三第一它逻辑直白调试容易特别适合比赛刚开始时快速确认题意理解没跑偏第二代码短键盘敲得快的话20秒写完不会因为语法错误浪费时间第三有的变体题比如要求把DP数组完整打印输出用来自查的用O(n²)反而更直观。当然如果你明确看到n10^5、10^6或者题目时间限制特别紧那就别犹豫直接上贪心二分。我自己的习惯是不确定数据规模能不能过的时候先把O(n²)写出来跑一遍样例再根据数据范围决定要不要改写成优化版本。这不丢人竞赛里这叫“先保底再冲高”。3. 进阶模板贪心 二分的O(n log n)解法3.1 核心观察维护一个“末尾最小”数组O(n²)慢就慢在每次更新dp[i]都要回头遍历所有j。能不能不遍历答案藏在一种贪心思想里。我维护一个数组tail其中tail[i]表示“长度为i1的递增子序列中末尾元素的最小值”。这个定义是LIS进阶解法的灵魂很多人背模板没背懂就是卡在这个概念上。我给你打个比方。假设你是幼儿园老师要给孩子们排队做操队伍越整齐越好每个孩子都比前面一个孩子高。现在不断有新人进来你的策略是如果新人身高特别高比现在所有队伍的最高末尾都高那就在后面新增一列队伍长度加一否则就在现有的队伍里找一个位置把他替换掉——替换成他之后这个位置的末尾身高只会变小或持平不会变大。这样一来队伍长度能保持尽可能长的状态而末尾身高一直被压到最低为后续更高的孩子预留空间。映射回代码就是遍历数组的每个元素x在tail里用二分查找找到第一个大于等于x的位置lower_bound。如果这个位置不存在也就是x比tail里所有数都大那就push_back到末尾tail长度加一如果存在就把那个位置的数替换成x。最后一轮循环结束后tail的长度就是LIS的长度。3.2 模板代码逐行精讲// O(n log n) LIS适合 n 10^6 int lengthOfLIS(vectorint a) { vectorint tail; for (int x : a) { auto it lower_bound(tail.begin(), tail.end(), x); if (it tail.end()) { tail.push_back(x); } else { *it x; } } return (int)tail.size(); }就这么点代码八九行但每一行都有讲究。先说lower_bound查的是什么——它查的是“第一个大于等于x的位置”。为什么是大于等于不是大于因为我们这里是严格递增tail里已经有值等于x时x就不能接在它后面但x作为“末尾最小值”对这一个位置来说比原来的值更小或相等替换掉没有坏处。如果你处理的是非严格递增把lower_bound改成upper_bound查“第一个大于x的位置”就允许相等值继续向后接了。这个细节我后面还会再强调。再说push_back条件。it tail.end()意思是在整个tail数组里都没找到大于等于x的数说明x比所有已知递增子序列的末尾都要大。这时候x就可以作为新长度的末尾把length1。比如tail现在是[1, 3, 5]来了个x6lower_bound找不到于是变成[1, 3, 5, 6]长度从3涨到4。最后是替换逻辑。it不等于end的时候把*it x。有人问替换掉会不会把之前的结果搞丢了不会因为tail存的是“某长度下末尾最小值”我们不关心这个最小值是从哪个位置来的、前面接了什么。只要这个长度的递增子序列的末尾被压得更小未来就更有可能接上新的元素。这正是贪心正确性的核心同一个长度下末尾越小越优。3.3 为什么这套模板是对的不变式的证明思路很多人学算法喜欢直接背代码但面试的时候面试官一句“为什么lower_bound能保证正确性”就能问懵一片。我这里给个简明的不变式证明思路不需要你背完整数学证明理解逻辑即可。循环开始前tail为空性质显然成立。每轮循环处理一个x我们维护的tail始终满足tail[i]是已扫描元素中长度为i1的递增子序列的最小可能末尾并且tail数组本身是严格递增的。为什么tail严格递增因为如果存在i j但tail[i] tail[j]那长度为j1的子序列里前i1个元素构成的子序列末尾一定小于等于tail[j] ≤ tail[i]说明存在更优的长度为i1的序列与tail[i]的定义矛盾。所以tail天然有序。既然tail有序就能二分。通过lower_bound找到替换位置要么扩展新长度要么压低某长度的末尾。每一轮操作后tail数组依然满足上述不变式。所以循环结束tail.size()就是全体元素中能构成的最长递增子序列长度。这个证明思路在面试时说清楚比背样例有用十倍。3.4 性能实测从10^4到10^6的飞跃我拿同样的数据实测过。n10^4O(n²)大约需要5000万次操作跑下来大约0.2秒看着还能忍。n10^5500亿次操作直接要20多秒正常OJ早超时了。换成贪心二分n10^5本地跑大概0.005秒n10^6也就0.05秒左右。这个差距是质变的不是十倍的差距是几千倍的差距。所以如果你要参加的是对时间有硬性要求的竞赛或者大厂笔试这套O(n log n)模板必须练到闭着眼睛能写出来。我建议你把它背下来之后再手写个三五遍直到出错率降到零。4. 路径还原从求长度到输出序列4.1 为什么长度容易、序列难只求长度的时候贪心二分模板几秒钟搞定。但很多题会追加一句“输出任意一个最长递增子序列”——这时候麻烦来了。麻烦在哪因为tail数组只是记录“某长度下的最小末尾值”它本身并不构成一个真实的递增子序列。我举个反例感受一下。a [2, 1, 3]跑一遍模板x2tail[2]x1替换tail[1]x3tail[1,3]长度2。但是tail数组是[1,3]而真实存在的长度为2的递增子序列是[2,3]或者[1,3]都没有问题恰好对得上。换个例子a [3, 1, 2]x3tail[3]x1tail[1]x2tail[1,2]。tail[1,2]是真实存在的子序列吗是[1,2]确实是。但换个刁钻一点的a [2, 5, 1, 3, 4]跑完模板tail[1,3,4]确实也是真实子序列。是不是总能对上答案是否定的。考虑a [1, 3, 5, 2, 4]跑模板1→tail[1]3→[1,3]5→[1,3,5]2→[1,2,5]这里2替换3注意这个tail可不是真实子序列因为原顺序里1后面没有跟着24→[1,2,4]4替换5。tail[1,2,4]长度3但数组里真的存在[1,2,4]这个子序列吗不存在1后面原数组中是3和5没有2。tail数组已经是抽象的东西了它只保证“存在某个长度为3的递增子序列”但它自己不一定就是那个子序列本身。这就是为什么输出序列需要另存一套信息。4.2 用pos数组记录每个元素的“归宿位置”思路其实不复杂。我们在跑贪心二分的时候每处理一个元素a[i]都会得到一个它在tail里的更新位置pos[i]——也就是这次替换或者push_back压到的下标。这个pos[i]保存下来它就是“以a[i]结尾的最长递增子序列的长度减一”。具体做法在lower_bound之后用int idx it - tail.begin()记录位置然后无论push还是替换都让pos[i] idx。循环结束后tail.size()就是最终答案长度len。要从后往前还原序列从原数组末尾倒着遍历如果pos[i] len-1说明a[i]可以作为长度为len的递增子序列的最后一个元素把它放进答案数组的最后一个位置然后len--。继续往前找pos[i] len-1的元素直到len减到0。为什么是从后往前因为我们从后往前找保证找出来的元素的相对顺序和原数组一致。如果你从前往后找可能找到的pos刚好递增但值不递增因为pos只告诉你在tail中的位置没告诉你值的大小关系。倒着找的时候由于我们在tail里的替换总是保证tail递增所以pos大的元素对应的值一定大于pos小的顺序天然正确。4.3 完整代码模板与易错点// 输出任意一个LIS序列 vectorint getLIS(vectorint a) { int n a.size(); if (n 0) return {}; vectorint tail, pos(n); for (int i 0; i n; i) { auto it lower_bound(tail.begin(), tail.end(), a[i]); int idx it - tail.begin(); if (it tail.end()) { tail.push_back(a[i]); } else { *it a[i]; } pos[i] idx; } int len tail.size(); vectorint ans(len); for (int i n - 1; i 0 len 0; i--) { if (pos[i] len - 1) { ans[len - 1] a[i]; len--; } } return ans; }这个模板里最阴间的坑是什么是条件if (pos[i] len - 1)。注意len是在循环中递减的第一次找的是第len-1个位置找到了之后len变成len-1接下来找的是新的len-1位置。这样能保证依次填出原序列。但你要小心如果pos[i]的值和len-1相等但pos[i]对应的a[i]并不一定比已经找到的答案数组中最后一个元素小……等等这里我解释一下——由于tail是严格递增的pos大的tail值一定大而tail[i]就是某个序列的末尾最小值实际填进ans的元素是a[i]本身a[i]虽然可能比tail[pos[i]]大但它一定满足和下一轮找到的更小pos对应的a[j]构成递增关系吗这里有个最经典的翻车点模板这套倒推法能保证找到正确答案但如果你不理解tail数组的语义很容易在证明上卡住。我直接给你结论这个方法在竞赛中被广泛使用是可靠的。但如果你想要一个理解起来更直观、更不容易在面试时候被人问倒的求序列做法建议你在O(n²)DP的同时维护prev数组一步一步回溯。O(n log n)的倒推法适合竞赛抢时间O(n²)的prev法适合教学和面试场景。看你的目标取舍。4.4 路径还原的备选方案O(n²) DP加前驱数组如果你用O(n²)的DP求具体序列更简单也更不容易出错。多开一个pre数组pre[i]记录转移来源的下标。当dp[i]被dp[j]1更新时pre[i] j。最后找到dp值最大的那个下标i从i一路往回跳pre把沿途的元素收集起来再反转就是整个LIS序列。vectorint getLIS_DP(vectorint a) { int n a.size(); vectorint dp(n, 1), pre(n, -1); int maxPos 0; for (int i 0; i n; i) { for (int j 0; j i; j) { if (a[j] a[i] dp[j] 1 dp[i]) { dp[i] dp[j] 1; pre[i] j; } } if (dp[i] dp[maxPos]) maxPos i; } vectorint ans; for (int cur maxPos; cur ! -1; cur pre[cur]) { ans.push_back(a[cur]); } reverse(ans.begin(), ans.end()); return ans; }两种方案各有适用场景。数据量小时我推荐用这个DP版出错几乎不可能。数据量大到必须用O(n log n)时再用pos倒推法但要记得自己先拿几个小样例手工验证一遍。5. LIS题集变体题型拆解与解题策略速记5.1 非严格递增LIS一个函数的差别最常遇到的变体是把“严格递增”改成“非严格递增”也就是a[i] a[j]也能接。结构上完全不需要改思路只需要改一个函数把lower_bound改成upper_bound。为什么非严格递增允许相等值连续出现。tail数组里已经有x的时候新来的x可以接在与它相同值的元素后面而不是替换它。upper_bound找的是第一个大于x的位置对相等的值它会直接跳过让x接在后面实现“长度1”的扩展效果。这个差别就是LeetCode上一堆中等难度题的测试点。我建议你把两个模板都背下来然后做两道对比题感受一下。一道是“最长递增子序列”的标准版另一道是“最长非递减子序列”。你会发现除了这一个函数其余代码一模一样。这个敏感度很重要——很多题目不是直接告诉你“严格”还是“非严格”而是藏在“可以相等”之类的条件里读题的时候务必画出来。5.2 二维LIS套娃信封问题LeetCode 354题“俄罗斯套娃信封问题”是LIS的经典二维升级版。每个信封有宽w和高h一个信封能装下另一个当且仅当宽和高都严格大于。问最多能嵌套多少个。思路是排序一维LIS。先把信封按宽度升序排宽度相同按高度降序排。然后只对高度数组做LIS。这里为什么宽度相同要高度降序因为宽度相同时两个信封不能互相嵌套——宽度必须严格大于相等也不行。如果按高度升序排两个宽度相等的信封会被错误地看成可以嵌套的递增序列。降序排列后高度数组的优势被保证宽度相等的高度是递减的不会形成一个伪递增子序列。这个细节是这道题最大的坑每年都有一堆人在上面栽跟头。二维LIS的模板思路能扩展到更多维度比如二维平面上选最多的点使得x和y同时递增代价是把排序规则改一下。这种题在竞赛里叫最长偏序链是一个延展性很强的模型。5.3 树状数组优化的LIS当贪心二分不适用时贪心二分的复杂度是O(n log n)这已经很快了但有一部分LIS变体不能用这套模板——因为tail数组的替换逻辑只在“比较数值大小”时有效如果你的比较规则不是简单的数而是一个二维偏序下的条件贪心二分就很难直接套。这时候用树状数组优化O(n²)DP就成了标准解法。思路是离散化数组值把每个值映射成树状数组的索引。然后从左到右扫描查询树状数组中“所有小于当前值的索引”的最大dp值加1后就是dp[i]再把dp[i]更新到树状数组对应位置。整个复杂度O(n log n)但因为树状数组能支持条件查询扩展性比贪心二分强得多。树状数组版的模板我简单写个伪代码思路离散化a得到rank树状数组bit长度为nfor x in a的rank值best bit.query(x-1)dp[i] best 1bit.update(x, dp[i])。这版在处理“要求输出每个位置局部LIS长度”之类的题里特别好用。更长远的看如果你掌握了树状数组优化DP的套路以后再遇到二维树状数组、带权值的LIS、带修改的LIS都能往下钻。它比贪心二分的可扩展性好但写起来代码量也更大。两个模板都值得存进你的算法仓库。5.4 LIS计数与带权LIS除了求长度和序列还有几个常考变体值得提一嘴。第一个是“最长递增子序列的个数”LeetCode 673。这个在O(n²)DP里好做多维护一个cnt[i]表示以a[i]结尾的最长递增子序列的方案数转移的时候如果dp[j]1 dp[i]cnt[i]清零重新设为cnt[j]如果dp[j]1 dp[i]cnt[i]累加cnt[j]。最后把所有长度等于全局最大值的dp[i]对应的cnt[i]加起来。这个题用贪心二分也能做但计数细节非常多稍不注意就重复统计。第二个是“带权LIS”每个元素除了值还有权重要求递增子序列的权重之和最大。这种题直接用贪心二分就不灵了因为tail数组只关注末尾最小值不关注权重累积但树状数组版本可以轻松适配bit.query(x-1)返回的不再是最大长度而是最大权重和然后update(x, val w[i])。这个模型在现实里很常见比如任务调度里在保证时序递增的前提下总收益最大。5.5 综合题单推荐基于我的实际刷题经验给你一张直接可以照着刷的LIS题单。每个题后面标注考察点刷完基本LIS的花样就全见过了。LeetCode 300标准LIS入门首刷严格递增求长度。LeetCode 674最长连续递增子序列用来区分“连续”与“不连续”的区别。LeetCode 673LIS数量统计理解计数DP。LeetCode 354套娃信封二维排序LIS。LeetCode 646最长数对链本质LIS但排序规则要自己想。LeetCode 面试题17.08马戏团人塔套娃信封换皮。洛谷 P1020导弹拦截第一问LIS第二问要转成“最长不升子序列”的贪心覆盖。洛谷 P3902递增n到10^5练习O(n log n)模板。洛谷 P1233木棍加工二维偏序贪心覆盖问题。刷这些题的时候有个经验法则先把所有题的题面里的“递增”“非递减”“严格”“连续”这些词全部圈出来归类之后再去刷。这样做一遍比盲目刷几十道题都管用——因为你看清了一个问题的骨架再换皮你也能认出来。5.6 刷题模板的调试心得最后分享两条实用的备考小技巧。第一个写LIS模板的时候一开始先在本地把tail数组打印出来调式确认每个x进入后tail的变化符合预期。这个习惯能让你快速发现自己是否把lower_bound和upper_bound搞混了。第二个自测用例千万别只写“正常序列”多测几个边界空数组、单个元素、全部相等、严格递减、末尾最大、开头最小、数字有重复。我有一次就是没测重复元素的情况结果在LeetCode上被一个“全部相等”的样例卡到怀疑人生。6. 常见问题与排查技巧实录这部分记几个我实际带人刷题时经常被问到的坑每一个都是真实踩过的不是教科书里的标准问题。6.1 lower_bound还是upper_bound用错了怎么排查这是出现频率最高的问题。症状是跑标准LIS模板结果比答案偏小或者偏大。排查方法分三步。先打印tail数组看每轮更新后它变成了什么。如果你发现两个值相等时新值把旧值顶掉了说明你在严格递增的题里用了upper_bound如果你发现相等值还能往tail后面接说明你在非严格递增的题里用了lower_bound。修正很容易把边界函数换一下即可。但根子上要理解两种题型的语义区别不然换个题目又错。6.2 tail数组初始化的常见误区有人习惯给tail初始化为一个极大值比如INT_MAX或者在尾部放一个哨兵。这个做法偶尔能跑通但非常危险。因为tail的语义是“动态增长的数组”初始为空每一轮根据实际读到的x决定是扩展还是替换。如果你预先塞了一个极大的数进去lower_bound永远能找到位置push_back的分支永远不会执行整个逻辑就歪了。我建议不要用哨兵直接从空数组开始。6.3 路径还原时输出序列不对怎么办如果你用pos倒推法输出了一个看起来不对的序列先检查两个地方。第一pos[i]的赋值时机——必须是在每次处理a[i]时记录lower_bound返回的idx不管有没有发生替换都要记。第二倒推循环的条件——必须是pos[i] len - 1不是pos[i] tail.size() - 1因为len在循环中不断变小指向当前要找的位置。还有一个很隐蔽的坑如果数组里有重复值倒推时可能会跳过某个本该选中的元素导致输出的序列长度不足。遇到这种情况我的建议是直接改用DP版维护pre数组逻辑更透明不容易出错。6.4 多组测试数据忘记清空竞赛里经常有“多组测试样例”的题目每组先给一个n再给n个数。不少人在循环里用了全局数组保存结果结果第二组数据开始时就带着上一组的数据一起算了。这个问题LIS模板里特别容易犯因为tail和pos都是局部变量还好但如果你图方便定义成全局变量一定记得在每组开始时resize或者clear。我自己的习惯是所有临时数据结构都在while循环内部定义天然自动销毁从根上杜绝残留。收尾一点个人心得把这套东西讲完我再说点题外话。LIS大概是整个算法学习路径里性价比最高的知识点之一因为它从最基础的DP一路能延伸出贪心、二分、树状数组、路径还原、计数DP全是一环扣一环的东西。你把它学透了相当于把一大块动态规划的地基都打牢了。我刷题这么多年遇到过无数看起来很难的题最后追根溯源底层模型就是个LIS变体。这也解释了为什么面试官和出题人这么偏爱它——考这一个点就能检测出你写代码的严谨程度、对边界的敏感度以及底层模型的迁移能力。如果你的时间有限至少把这篇文章里的O(n log n)模板背熟把pos数组那一节弄明白再把套娃信封那道题做了。这三样足够你在大部分实战场景中不拉胯。剩下的就交给刷题量去积累手感吧。 
长河君 · 2026/10/8 3:40:02 · 阅读 1.2k 最长递增子序列(LIS)全解：从O(n²)动态规划到贪心二分优化与路径还原
最长递增子序列圈内都叫它LIS全称Longest Increasing Subsequence。这名字看着学术其实特别接地气——就是给你一个乱序数组让你在里面挑一些数出来保持相对顺序不变组成一个严格递增的序列问这个序列最长能有多长。就这么个问题从大一数据结构课到大厂面试手撕代码再到蓝桥杯、ACM区域赛到处都是它的影子。今天我把这东西彻底讲透从朴素的动态规划到能跑百万级数据的贪心二分模板再附上我这些年刷题攒下来的变体题单和解法要点一篇文给你安排明白。这篇东西适合谁看刚学DP的大一选手面试前突击算法的求职党还有刷LeetCode和竞赛题卡在LIS变体上的老手。看完你能收获三样东西一套不会写错的O(n log n)模板一份覆盖各种花式考法的题集拆解以及一堆别人博客里不常写的坑和心得。1. LIS问题的本质与适用场景判断先把这个问题的本质聊清楚。LIS不是一个孤立的“背模板题”它背后是动态规划里极有代表性的一类模型——以某个位置结尾的最优子结构。你在纸上随便写一串数比如[3, 1, 2, 1, 8, 5, 6]肉眼扫一遍能看出最长上升子序列是[1, 2, 5, 6]或者[1, 2, 1, 5, 6]不对[1, 2, 1]中间那个1就断了严格递增不能相等。所以答案是[1, 2, 5, 6]或者[1, 2, 8]后者长度3前者长度4答案长度就是4。这个例子里藏了两个关键信息第一子序列不要求连续跳着选但顺序不能乱第二题目说的是“严格递增”也就是必须a[i] a[j]等于都不行。很多新手在这俩地方栽跟头——把“子序列”理解成“子数组”或者把“严格递增”直接放宽成“非递减”。这不是审题粗心的问题是你对模型的定义边界不清楚。后面讲变体的时候你会看到非严格递增的情况改一行代码就能处理但那是另一个问题不是LIS本身。判断一道题到底要不要用LIS模型我有个习惯先看数据规模。如果n在10^3级别O(n²)的DP可以过随便写。如果n到了10^5甚至10^6那基本就是在明着告诉你必须上O(n log n)的贪心二分做法。再看题意凡是“选出尽可能多的元素满足某种递增/偏序关系”的十有八九是LIS或者它的二维亲戚。比如套娃信封、最长数对链、合唱队形、删数使数组有序都能归到这一类。还有一个容易被忽略的判断维度问题要求返回什么。只问长度模板直接返回tail.size()轻松。要求输出具体序列就得额外维护一个pos数组做路径还原。要求统计方案数还得再维护一个计数数组。我见过不少人拿到“输出具体序列”就直接懵了因为平时只背了求长度的模板没看里层的原理。所以这篇文章后面会专门用一节讲路径还原这是从“会背模板”到“真正会做”的分水岭。2. 入门解法O(n²)动态规划2.1 状态设计与转移方程推导咱们先别急着上最优解法O(n²)的DP虽然慢但它是理解一切LIS变体的地基。而且小数据量下它写起来极其简单几乎不可能出错抢时间的时候反而好用。定义状态dp[i]表示“以第i个位置的数字作为结尾的最长递增子序列的长度”。注意是以a[i]结尾不是“前i个数字里能选出的最长长度”。这两个概念的区别很微妙但至关重要。以a[i]结尾意味着你选的这个子序列里最后一个元素必须是a[i]。这样定义的好处是转移的时候只用看前面的状态不用管后面的元素。转移方程长这样dp[i] max(dp[j] 1) 其中 0 ≤ j i 且 a[j] a[i]这句话翻译成人话就是我想知道以a[i]结尾能最长到多少就去前面遍历每一个a[j]如果a[j]比a[i]小满足递增条件那我可以把a[j]接在某个以a[j]结尾的递增子序列后面长度就是dp[j] 1。把所有满足条件的j都试一遍取最大值。如果前面一个满足条件的都没有dp[i]就保持初始值1——单个元素本身就是一个长度为1的递增子序列。这方程看着简单但我见过大量学生写错一个地方初始化。dp数组要全部初始化为1而不是0。原因就是上面说的任何单个元素自身构成长度为1的子序列。你要是初始化成0整个转移就全错了最后答案永远是0。2.2 代码实现与复杂度分析// O(n^2) LIS适合 n 1000 int lengthOfLIS(vectorint a) { int n a.size(); if (n 0) return 0; vectorint dp(n, 1); int ans 1; for (int i 0; i n; i) { for (int j 0; j i; j) { if (a[j] a[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; }这个写法里有两个容易翻车的细节。第一ans的更新要在内层循环结束之后用dp[i]去更新全局答案因为dp[i]可能比之前所有dp都大。第二内层循环遍历j的时候a[j] a[i]这个条件是严格小于不是小于等于。如果你处理的是非严格递增LIS这里就要改成a[j] a[i]。就这么一个符号的区别能让你在一道题上栽半个小时。复杂度很好算两层循环外层n次内层平均n/2次总的就是O(n²)空间O(n)。n1000的时候大概50万次运算眨眼功夫。但n10^5的时候是10^10次服务器都得卡几秒这时候就必须换更快的做法了。2.3 什么时候该用O(n²)而不是贪心二分很多人以为O(n log n)永远优于O(n²)所以直接背高级模板就完事了。但实际做题的时候我反而经常先写O(n²)。原因有三第一它逻辑直白调试容易特别适合比赛刚开始时快速确认题意理解没跑偏第二代码短键盘敲得快的话20秒写完不会因为语法错误浪费时间第三有的变体题比如要求把DP数组完整打印输出用来自查的用O(n²)反而更直观。当然如果你明确看到n10^5、10^6或者题目时间限制特别紧那就别犹豫直接上贪心二分。我自己的习惯是不确定数据规模能不能过的时候先把O(n²)写出来跑一遍样例再根据数据范围决定要不要改写成优化版本。这不丢人竞赛里这叫“先保底再冲高”。3. 进阶模板贪心 二分的O(n log n)解法3.1 核心观察维护一个“末尾最小”数组O(n²)慢就慢在每次更新dp[i]都要回头遍历所有j。能不能不遍历答案藏在一种贪心思想里。我维护一个数组tail其中tail[i]表示“长度为i1的递增子序列中末尾元素的最小值”。这个定义是LIS进阶解法的灵魂很多人背模板没背懂就是卡在这个概念上。我给你打个比方。假设你是幼儿园老师要给孩子们排队做操队伍越整齐越好每个孩子都比前面一个孩子高。现在不断有新人进来你的策略是如果新人身高特别高比现在所有队伍的最高末尾都高那就在后面新增一列队伍长度加一否则就在现有的队伍里找一个位置把他替换掉——替换成他之后这个位置的末尾身高只会变小或持平不会变大。这样一来队伍长度能保持尽可能长的状态而末尾身高一直被压到最低为后续更高的孩子预留空间。映射回代码就是遍历数组的每个元素x在tail里用二分查找找到第一个大于等于x的位置lower_bound。如果这个位置不存在也就是x比tail里所有数都大那就push_back到末尾tail长度加一如果存在就把那个位置的数替换成x。最后一轮循环结束后tail的长度就是LIS的长度。3.2 模板代码逐行精讲// O(n log n) LIS适合 n 10^6 int lengthOfLIS(vectorint a) { vectorint tail; for (int x : a) { auto it lower_bound(tail.begin(), tail.end(), x); if (it tail.end()) { tail.push_back(x); } else { *it x; } } return (int)tail.size(); }就这么点代码八九行但每一行都有讲究。先说lower_bound查的是什么——它查的是“第一个大于等于x的位置”。为什么是大于等于不是大于因为我们这里是严格递增tail里已经有值等于x时x就不能接在它后面但x作为“末尾最小值”对这一个位置来说比原来的值更小或相等替换掉没有坏处。如果你处理的是非严格递增把lower_bound改成upper_bound查“第一个大于x的位置”就允许相等值继续向后接了。这个细节我后面还会再强调。再说push_back条件。it tail.end()意思是在整个tail数组里都没找到大于等于x的数说明x比所有已知递增子序列的末尾都要大。这时候x就可以作为新长度的末尾把length1。比如tail现在是[1, 3, 5]来了个x6lower_bound找不到于是变成[1, 3, 5, 6]长度从3涨到4。最后是替换逻辑。it不等于end的时候把*it x。有人问替换掉会不会把之前的结果搞丢了不会因为tail存的是“某长度下末尾最小值”我们不关心这个最小值是从哪个位置来的、前面接了什么。只要这个长度的递增子序列的末尾被压得更小未来就更有可能接上新的元素。这正是贪心正确性的核心同一个长度下末尾越小越优。3.3 为什么这套模板是对的不变式的证明思路很多人学算法喜欢直接背代码但面试的时候面试官一句“为什么lower_bound能保证正确性”就能问懵一片。我这里给个简明的不变式证明思路不需要你背完整数学证明理解逻辑即可。循环开始前tail为空性质显然成立。每轮循环处理一个x我们维护的tail始终满足tail[i]是已扫描元素中长度为i1的递增子序列的最小可能末尾并且tail数组本身是严格递增的。为什么tail严格递增因为如果存在i j但tail[i] tail[j]那长度为j1的子序列里前i1个元素构成的子序列末尾一定小于等于tail[j] ≤ tail[i]说明存在更优的长度为i1的序列与tail[i]的定义矛盾。所以tail天然有序。既然tail有序就能二分。通过lower_bound找到替换位置要么扩展新长度要么压低某长度的末尾。每一轮操作后tail数组依然满足上述不变式。所以循环结束tail.size()就是全体元素中能构成的最长递增子序列长度。这个证明思路在面试时说清楚比背样例有用十倍。3.4 性能实测从10^4到10^6的飞跃我拿同样的数据实测过。n10^4O(n²)大约需要5000万次操作跑下来大约0.2秒看着还能忍。n10^5500亿次操作直接要20多秒正常OJ早超时了。换成贪心二分n10^5本地跑大概0.005秒n10^6也就0.05秒左右。这个差距是质变的不是十倍的差距是几千倍的差距。所以如果你要参加的是对时间有硬性要求的竞赛或者大厂笔试这套O(n log n)模板必须练到闭着眼睛能写出来。我建议你把它背下来之后再手写个三五遍直到出错率降到零。4. 路径还原从求长度到输出序列4.1 为什么长度容易、序列难只求长度的时候贪心二分模板几秒钟搞定。但很多题会追加一句“输出任意一个最长递增子序列”——这时候麻烦来了。麻烦在哪因为tail数组只是记录“某长度下的最小末尾值”它本身并不构成一个真实的递增子序列。我举个反例感受一下。a [2, 1, 3]跑一遍模板x2tail[2]x1替换tail[1]x3tail[1,3]长度2。但是tail数组是[1,3]而真实存在的长度为2的递增子序列是[2,3]或者[1,3]都没有问题恰好对得上。换个例子a [3, 1, 2]x3tail[3]x1tail[1]x2tail[1,2]。tail[1,2]是真实存在的子序列吗是[1,2]确实是。但换个刁钻一点的a [2, 5, 1, 3, 4]跑完模板tail[1,3,4]确实也是真实子序列。是不是总能对上答案是否定的。考虑a [1, 3, 5, 2, 4]跑模板1→tail[1]3→[1,3]5→[1,3,5]2→[1,2,5]这里2替换3注意这个tail可不是真实子序列因为原顺序里1后面没有跟着24→[1,2,4]4替换5。tail[1,2,4]长度3但数组里真的存在[1,2,4]这个子序列吗不存在1后面原数组中是3和5没有2。tail数组已经是抽象的东西了它只保证“存在某个长度为3的递增子序列”但它自己不一定就是那个子序列本身。这就是为什么输出序列需要另存一套信息。4.2 用pos数组记录每个元素的“归宿位置”思路其实不复杂。我们在跑贪心二分的时候每处理一个元素a[i]都会得到一个它在tail里的更新位置pos[i]——也就是这次替换或者push_back压到的下标。这个pos[i]保存下来它就是“以a[i]结尾的最长递增子序列的长度减一”。具体做法在lower_bound之后用int idx it - tail.begin()记录位置然后无论push还是替换都让pos[i] idx。循环结束后tail.size()就是最终答案长度len。要从后往前还原序列从原数组末尾倒着遍历如果pos[i] len-1说明a[i]可以作为长度为len的递增子序列的最后一个元素把它放进答案数组的最后一个位置然后len--。继续往前找pos[i] len-1的元素直到len减到0。为什么是从后往前因为我们从后往前找保证找出来的元素的相对顺序和原数组一致。如果你从前往后找可能找到的pos刚好递增但值不递增因为pos只告诉你在tail中的位置没告诉你值的大小关系。倒着找的时候由于我们在tail里的替换总是保证tail递增所以pos大的元素对应的值一定大于pos小的顺序天然正确。4.3 完整代码模板与易错点// 输出任意一个LIS序列 vectorint getLIS(vectorint a) { int n a.size(); if (n 0) return {}; vectorint tail, pos(n); for (int i 0; i n; i) { auto it lower_bound(tail.begin(), tail.end(), a[i]); int idx it - tail.begin(); if (it tail.end()) { tail.push_back(a[i]); } else { *it a[i]; } pos[i] idx; } int len tail.size(); vectorint ans(len); for (int i n - 1; i 0 len 0; i--) { if (pos[i] len - 1) { ans[len - 1] a[i]; len--; } } return ans; }这个模板里最阴间的坑是什么是条件if (pos[i] len - 1)。注意len是在循环中递减的第一次找的是第len-1个位置找到了之后len变成len-1接下来找的是新的len-1位置。这样能保证依次填出原序列。但你要小心如果pos[i]的值和len-1相等但pos[i]对应的a[i]并不一定比已经找到的答案数组中最后一个元素小……等等这里我解释一下——由于tail是严格递增的pos大的tail值一定大而tail[i]就是某个序列的末尾最小值实际填进ans的元素是a[i]本身a[i]虽然可能比tail[pos[i]]大但它一定满足和下一轮找到的更小pos对应的a[j]构成递增关系吗这里有个最经典的翻车点模板这套倒推法能保证找到正确答案但如果你不理解tail数组的语义很容易在证明上卡住。我直接给你结论这个方法在竞赛中被广泛使用是可靠的。但如果你想要一个理解起来更直观、更不容易在面试时候被人问倒的求序列做法建议你在O(n²)DP的同时维护prev数组一步一步回溯。O(n log n)的倒推法适合竞赛抢时间O(n²)的prev法适合教学和面试场景。看你的目标取舍。4.4 路径还原的备选方案O(n²) DP加前驱数组如果你用O(n²)的DP求具体序列更简单也更不容易出错。多开一个pre数组pre[i]记录转移来源的下标。当dp[i]被dp[j]1更新时pre[i] j。最后找到dp值最大的那个下标i从i一路往回跳pre把沿途的元素收集起来再反转就是整个LIS序列。vectorint getLIS_DP(vectorint a) { int n a.size(); vectorint dp(n, 1), pre(n, -1); int maxPos 0; for (int i 0; i n; i) { for (int j 0; j i; j) { if (a[j] a[i] dp[j] 1 dp[i]) { dp[i] dp[j] 1; pre[i] j; } } if (dp[i] dp[maxPos]) maxPos i; } vectorint ans; for (int cur maxPos; cur ! -1; cur pre[cur]) { ans.push_back(a[cur]); } reverse(ans.begin(), ans.end()); return ans; }两种方案各有适用场景。数据量小时我推荐用这个DP版出错几乎不可能。数据量大到必须用O(n log n)时再用pos倒推法但要记得自己先拿几个小样例手工验证一遍。5. LIS题集变体题型拆解与解题策略速记5.1 非严格递增LIS一个函数的差别最常遇到的变体是把“严格递增”改成“非严格递增”也就是a[i] a[j]也能接。结构上完全不需要改思路只需要改一个函数把lower_bound改成upper_bound。为什么非严格递增允许相等值连续出现。tail数组里已经有x的时候新来的x可以接在与它相同值的元素后面而不是替换它。upper_bound找的是第一个大于x的位置对相等的值它会直接跳过让x接在后面实现“长度1”的扩展效果。这个差别就是LeetCode上一堆中等难度题的测试点。我建议你把两个模板都背下来然后做两道对比题感受一下。一道是“最长递增子序列”的标准版另一道是“最长非递减子序列”。你会发现除了这一个函数其余代码一模一样。这个敏感度很重要——很多题目不是直接告诉你“严格”还是“非严格”而是藏在“可以相等”之类的条件里读题的时候务必画出来。5.2 二维LIS套娃信封问题LeetCode 354题“俄罗斯套娃信封问题”是LIS的经典二维升级版。每个信封有宽w和高h一个信封能装下另一个当且仅当宽和高都严格大于。问最多能嵌套多少个。思路是排序一维LIS。先把信封按宽度升序排宽度相同按高度降序排。然后只对高度数组做LIS。这里为什么宽度相同要高度降序因为宽度相同时两个信封不能互相嵌套——宽度必须严格大于相等也不行。如果按高度升序排两个宽度相等的信封会被错误地看成可以嵌套的递增序列。降序排列后高度数组的优势被保证宽度相等的高度是递减的不会形成一个伪递增子序列。这个细节是这道题最大的坑每年都有一堆人在上面栽跟头。二维LIS的模板思路能扩展到更多维度比如二维平面上选最多的点使得x和y同时递增代价是把排序规则改一下。这种题在竞赛里叫最长偏序链是一个延展性很强的模型。5.3 树状数组优化的LIS当贪心二分不适用时贪心二分的复杂度是O(n log n)这已经很快了但有一部分LIS变体不能用这套模板——因为tail数组的替换逻辑只在“比较数值大小”时有效如果你的比较规则不是简单的数而是一个二维偏序下的条件贪心二分就很难直接套。这时候用树状数组优化O(n²)DP就成了标准解法。思路是离散化数组值把每个值映射成树状数组的索引。然后从左到右扫描查询树状数组中“所有小于当前值的索引”的最大dp值加1后就是dp[i]再把dp[i]更新到树状数组对应位置。整个复杂度O(n log n)但因为树状数组能支持条件查询扩展性比贪心二分强得多。树状数组版的模板我简单写个伪代码思路离散化a得到rank树状数组bit长度为nfor x in a的rank值best bit.query(x-1)dp[i] best 1bit.update(x, dp[i])。这版在处理“要求输出每个位置局部LIS长度”之类的题里特别好用。更长远的看如果你掌握了树状数组优化DP的套路以后再遇到二维树状数组、带权值的LIS、带修改的LIS都能往下钻。它比贪心二分的可扩展性好但写起来代码量也更大。两个模板都值得存进你的算法仓库。5.4 LIS计数与带权LIS除了求长度和序列还有几个常考变体值得提一嘴。第一个是“最长递增子序列的个数”LeetCode 673。这个在O(n²)DP里好做多维护一个cnt[i]表示以a[i]结尾的最长递增子序列的方案数转移的时候如果dp[j]1 dp[i]cnt[i]清零重新设为cnt[j]如果dp[j]1 dp[i]cnt[i]累加cnt[j]。最后把所有长度等于全局最大值的dp[i]对应的cnt[i]加起来。这个题用贪心二分也能做但计数细节非常多稍不注意就重复统计。第二个是“带权LIS”每个元素除了值还有权重要求递增子序列的权重之和最大。这种题直接用贪心二分就不灵了因为tail数组只关注末尾最小值不关注权重累积但树状数组版本可以轻松适配bit.query(x-1)返回的不再是最大长度而是最大权重和然后update(x, val w[i])。这个模型在现实里很常见比如任务调度里在保证时序递增的前提下总收益最大。5.5 综合题单推荐基于我的实际刷题经验给你一张直接可以照着刷的LIS题单。每个题后面标注考察点刷完基本LIS的花样就全见过了。LeetCode 300标准LIS入门首刷严格递增求长度。LeetCode 674最长连续递增子序列用来区分“连续”与“不连续”的区别。LeetCode 673LIS数量统计理解计数DP。LeetCode 354套娃信封二维排序LIS。LeetCode 646最长数对链本质LIS但排序规则要自己想。LeetCode 面试题17.08马戏团人塔套娃信封换皮。洛谷 P1020导弹拦截第一问LIS第二问要转成“最长不升子序列”的贪心覆盖。洛谷 P3902递增n到10^5练习O(n log n)模板。洛谷 P1233木棍加工二维偏序贪心覆盖问题。刷这些题的时候有个经验法则先把所有题的题面里的“递增”“非递减”“严格”“连续”这些词全部圈出来归类之后再去刷。这样做一遍比盲目刷几十道题都管用——因为你看清了一个问题的骨架再换皮你也能认出来。5.6 刷题模板的调试心得最后分享两条实用的备考小技巧。第一个写LIS模板的时候一开始先在本地把tail数组打印出来调式确认每个x进入后tail的变化符合预期。这个习惯能让你快速发现自己是否把lower_bound和upper_bound搞混了。第二个自测用例千万别只写“正常序列”多测几个边界空数组、单个元素、全部相等、严格递减、末尾最大、开头最小、数字有重复。我有一次就是没测重复元素的情况结果在LeetCode上被一个“全部相等”的样例卡到怀疑人生。6. 常见问题与排查技巧实录这部分记几个我实际带人刷题时经常被问到的坑每一个都是真实踩过的不是教科书里的标准问题。6.1 lower_bound还是upper_bound用错了怎么排查这是出现频率最高的问题。症状是跑标准LIS模板结果比答案偏小或者偏大。排查方法分三步。先打印tail数组看每轮更新后它变成了什么。如果你发现两个值相等时新值把旧值顶掉了说明你在严格递增的题里用了upper_bound如果你发现相等值还能往tail后面接说明你在非严格递增的题里用了lower_bound。修正很容易把边界函数换一下即可。但根子上要理解两种题型的语义区别不然换个题目又错。6.2 tail数组初始化的常见误区有人习惯给tail初始化为一个极大值比如INT_MAX或者在尾部放一个哨兵。这个做法偶尔能跑通但非常危险。因为tail的语义是“动态增长的数组”初始为空每一轮根据实际读到的x决定是扩展还是替换。如果你预先塞了一个极大的数进去lower_bound永远能找到位置push_back的分支永远不会执行整个逻辑就歪了。我建议不要用哨兵直接从空数组开始。6.3 路径还原时输出序列不对怎么办如果你用pos倒推法输出了一个看起来不对的序列先检查两个地方。第一pos[i]的赋值时机——必须是在每次处理a[i]时记录lower_bound返回的idx不管有没有发生替换都要记。第二倒推循环的条件——必须是pos[i] len - 1不是pos[i] tail.size() - 1因为len在循环中不断变小指向当前要找的位置。还有一个很隐蔽的坑如果数组里有重复值倒推时可能会跳过某个本该选中的元素导致输出的序列长度不足。遇到这种情况我的建议是直接改用DP版维护pre数组逻辑更透明不容易出错。6.4 多组测试数据忘记清空竞赛里经常有“多组测试样例”的题目每组先给一个n再给n个数。不少人在循环里用了全局数组保存结果结果第二组数据开始时就带着上一组的数据一起算了。这个问题LIS模板里特别容易犯因为tail和pos都是局部变量还好但如果你图方便定义成全局变量一定记得在每组开始时resize或者clear。我自己的习惯是所有临时数据结构都在while循环内部定义天然自动销毁从根上杜绝残留。收尾一点个人心得把这套东西讲完我再说点题外话。LIS大概是整个算法学习路径里性价比最高的知识点之一因为它从最基础的DP一路能延伸出贪心、二分、树状数组、路径还原、计数DP全是一环扣一环的东西。你把它学透了相当于把一大块动态规划的地基都打牢了。我刷题这么多年遇到过无数看起来很难的题最后追根溯源底层模型就是个LIS变体。这也解释了为什么面试官和出题人这么偏爱它——考这一个点就能检测出你写代码的严谨程度、对边界的敏感度以及底层模型的迁移能力。如果你的时间有限至少把这篇文章里的O(n log n)模板背熟把pos数组那一节弄明白再把套娃信封那道题做了。这三样足够你在大部分实战场景中不拉胯。剩下的就交给刷题量去积累手感吧。