企业官网建设流程全解析

最长递增子序列，圈内都叫它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(vector<int>& a) { int n = a.size(); if (n == 0) return 0; vector<int> 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)。n=1000的时候大概50万次运算，眨眼功夫。但n=10^5的时候是10^10次，服务器都得卡几秒，这时候就必须换更快的做法了。

2.3 什么时候该用O(n²)而不是贪心二分

很多人以为O(n log n)永远优于O(n²)，所以直接背高级模板就完事了。但实际做题的时候，我反而经常先写O(n²)。原因有三：第一，它逻辑直白，调试容易，特别适合比赛刚开始时快速确认题意理解没跑偏；第二，代码短，键盘敲得快的话20秒写完，不会因为语法错误浪费时间；第三，有的变体题，比如要求把DP数组完整打印输出用来自查的，用O(n²)反而更直观。

当然，如果你明确看到n=10^5、10^6，或者题目时间限制特别紧，那就别犹豫，直接上贪心二分。我自己的习惯是：不确定数据规模能不能过的时候，先把O(n²)写出来跑一遍样例，再根据数据范围决定要不要改写成优化版本。这不丢人，竞赛里这叫“先保底再冲高”。

3. 进阶模板：贪心 + 二分的O(n log n)解法

3.1 核心观察：维护一个“末尾最小”数组

O(n²)慢就慢在，每次更新dp[i]都要回头遍历所有j。能不能不遍历？答案藏在一种贪心思想里。我维护一个数组tail，其中tail[i]表示“长度为i+1的递增子序列中，末尾元素的最小值”。这个定义是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(vector<int>& a) { vector<int> 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就可以作为新长度的末尾，把length+1。比如tail现在是[1, 3, 5]，来了个x=6，lower_bound找不到，于是变成[1, 3, 5, 6]，长度从3涨到4。

最后是替换逻辑。it不等于end的时候，把*it = x。有人问，替换掉会不会把之前的结果搞丢了？不会，因为tail存的是“某长度下末尾最小值”，我们不关心这个最小值是从哪个位置来的、前面接了什么。只要这个长度的递增子序列的末尾被压得更小，未来就更有可能接上新的元素。这正是贪心正确性的核心：同一个长度下，末尾越小，越优。

3.3 为什么这套模板是对的：不变式的证明思路

很多人学算法喜欢直接背代码，但面试的时候面试官一句“为什么lower_bound能保证正确性”就能问懵一片。我这里给个简明的不变式证明思路，不需要你背完整数学证明，理解逻辑即可。

循环开始前，tail为空，性质显然成立。每轮循环处理一个x，我们维护的tail始终满足：tail[i]是已扫描元素中，长度为i+1的递增子序列的最小可能末尾；并且tail数组本身是严格递增的。为什么tail严格递增？因为如果存在i < j但tail[i] >= tail[j]，那长度为j+1的子序列里，前i+1个元素构成的子序列末尾一定小于等于tail[j] ≤ tail[i]，说明存在更优的长度为i+1的序列，与tail[i]的定义矛盾。所以tail天然有序。

既然tail有序，就能二分。通过lower_bound找到替换位置，要么扩展新长度，要么压低某长度的末尾。每一轮操作后，tail数组依然满足上述不变式。所以循环结束，tail.size()就是全体元素中能构成的最长递增子序列长度。这个证明思路在面试时说清楚，比背样例有用十倍。

3.4 性能实测：从10^4到10^6的飞跃

我拿同样的数据实测过。n=10^4，O(n²)大约需要5000万次操作，跑下来大约0.2秒，看着还能忍。n=10^5，500亿次操作，直接要20多秒，正常OJ早超时了。换成贪心二分，n=10^5本地跑大概0.005秒，n=10^6也就0.05秒左右。这个差距是质变的，不是十倍的差距，是几千倍的差距。

所以如果你要参加的是对时间有硬性要求的竞赛或者大厂笔试，这套O(n log n)模板必须练到闭着眼睛能写出来。我建议你把它背下来之后，再手写个三五遍，直到出错率降到零。

4. 路径还原：从求长度到输出序列

4.1 为什么长度容易、序列难

只求长度的时候，贪心二分模板几秒钟搞定。但很多题会追加一句“输出任意一个最长递增子序列”——这时候麻烦来了。麻烦在哪？因为tail数组只是记录“某长度下的最小末尾值”，它本身并不构成一个真实的递增子序列。

我举个反例感受一下。a = [2, 1, 3]，跑一遍模板：x=2，tail=[2]；x=1，替换，tail=[1]；x=3，tail=[1,3]，长度2。但是tail数组是[1,3]，而真实存在的长度为2的递增子序列是[2,3]或者[1,3]，都没有问题，恰好对得上。换个例子：a = [3, 1, 2]，x=3，tail=[3]；x=1，tail=[1]；x=2，tail=[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后面没有跟着2）；4→[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序列 vector<int> getLIS(vector<int>& a) { int n = a.size(); if (n == 0) return {}; vector<int> 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(); vector<int> 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序列。

vector<int> getLIS_DP(vector<int>& a) { int n = a.size(); vector<int> 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; } vector<int> 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长度为n；for x in a的rank值，best = bit.query(x-1)，dp[i] = best + 1；bit.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 673：LIS数量统计，理解计数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数组那一节弄明白，再把套娃信封那道题做了。这三样足够你在大部分实战场景中不拉胯。剩下的，就交给刷题量去积累手感吧。