企业官网建设流程全解析

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数组的最大值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]表示长度为k+1的递增子序列中，最小的末尾元素值。

这个定义初看很抽象，我解释一下就通了。假设目前找到了长度为3的递增子序列，可能有多种组合，末尾值可能是5，也可能是8。这时候tails[2]就存5，因为长度为3的序列我们只关心最小的末尾是多少。为什么要最小？因为末尾越小，后面新元素越容易接上去，这个“保留最优候选”的思想就是贪心所在。

有个非常直观的类比：找LIS就像在一排牌桌上按顺序整理扑克牌，每张新牌来了，我们把它放到“最合适”的那堆牌上，规则是放到所有堆顶牌中第一张不小于它的牌上，如果没有就新开一堆。最后牌堆数就是LIS长度。这个玩法叫Patience Sorting（耐心排序），tails数组对应的就是每堆牌最上面的那张牌。

3.2 维护过程拆解：替换还是追加

tails数组的维护逻辑分为两种情况。对每个新元素x：

• x大于tails所有元素：说明找到了更长的递增子序列，把x追加到tails末尾，LIS长度加1。
• x不大于tails最大元素：在tails中二分查找第一个不小于x的位置，用x替换它。

替换这个动作是唯一看起来反常的地方。用前一个数组[10, 9, 2, 5, 3, 7, 101, 18]试一遍：

1. 10 → tails = [10]
2. 9 → 二分找到位置0，替换 → tails = [9]
3. 2 → 替换位置0 → tails = [2]
4. 5 → 大于2，追加 → tails = [2, 5]
5. 3 → 二分找到位置1（第一个不小于3的是5），替换 → tails = [2, 3]
6. 7 → 大于3，追加 → tails = [2, 3, 7]
7. 101 → 追加 → tails = [2, 3, 7, 101]
8. 18 → 二分找到位置3（第一个不小于18的是101），替换 → tails = [2, 3, 7, 18]

最终tails长度是4，与真值一致。仔细看，tails数组本身始终严格递增——这正是它能用二分查找的前提条件。

3.3 为什么替换不会破坏正确解

这是核心中的核心，面试官最爱深挖的地方。很多人不理解：在第5步把tails[1]从5替换成3时，等于丢弃了子序列[2, 5]，这个操作会不会导致最终答案丢失？

答案是不会，原因需要看清楚一点：tails[k]的含义从来不是“一个确定的、唯一的长度为k+1的序列”，而是“长度为k+1的所有递增子序列中，末尾能取得的最小值”。5和3代表长度2的序列有两种可能，3更好因为更小。而且替换这个动作不影响已经达到的长度——tails长度没变，只是把该长度的“底线”压得更低，让后续元素更容易构建更长的序列。

证明可以这样想：如果长度k存在某个末尾值为v的递增子序列，那么tails[k-1]一定小于v（因为子序列内部递增，倒数第二个元素必然小于v）。这保证了tails的严格递增结构。替换时，我们找到的是第一个不小于x的位置p，说明tails[p-1] < x，于是可以用tails[p-1]那个序列接上x，得到长度p+1、末尾为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这道题把三个问题都占了：目标函数是长度，状态必须记录末尾元素才能转移，二分优化说明贪心能奏效。能把这套思考框架迁移到其他题上，刷题才不会变成海量背题。