最长递增子序列LIS：动态规划与贪心二分解法全解析

力扣热题100里排在第87位的这道最长递增子序列，原题号其实是300. Longest Increasing Subsequence。我刷到这一题的时候有点意外——大名鼎鼎的LIS，居然在热题100里藏得这么靠后。不过位置靠后不代表它简单，这几乎是动态规划入门绕不开的关卡，也是面试里“线性dp”最常考的原型之一。更妙的是，它同时能让你看到动态规划和贪心两种截然不同的解题风格，一棵树上开两朵花。题目本身一句话就能说清楚：给定一个整数数组，找出其中最长严格递增子序列的长度。这里“子序列”不要求连续，但必须保持原始数组中的相对顺序。

如果你是刚开始刷动态规划的人，这道题值得作为“状态设计”的第一课；如果你已经在背模板、准备面试，那贪心加二分的写法就是你必须掌握的复杂度优化；再进一步，如果你想知道为什么有时候贪心数组里的内容并不能直接当答案输出，这篇文章也会把坑填上。

1. 题目解读与两种思路的全局观

1.1 先弄清楚“子序列”和“严格递增”意味着什么

给你一个例子就明白了。

nums = [10, 9, 2, 5, 3, 7, 101, 18]

它的最长递增子序列长度是4，比如[2, 3, 7, 101]，也可以是[2, 3, 7, 18]。注意这里跳过了很多数字，9和10因为出现在2之前，所以没法参与后续的递增；101虽然大，但18在它后面，所以如果选了101，后面只能走到101结束。

这里有两个关键词容易被新手忽略。

第一个是“子序列”。子序列不需要在原数组里连续，只要下标顺序不乱就行。所以你不能用“连续最大上升子数组”的思路去套。连续问题往往靠一个滑动窗口或一次遍历就能维护，但子序列问题天然就要考虑“跳过中间元素”的可能，这也是为什么线性dp会把每个位置当作一个独立状态来设计。

第二个是“严格递增”。严格递增意味着nums[j] < nums[i]，而不是<=。如果数组是[1, 1, 1]，答案不是3，而是1。很多人在二分优化那里翻车，就是因为没分清“严格递增”和“非递减”，后面我会专门讲。

1.2 为什么这道题值得用两种解法反复刷

这道题好在哪？好在它用最少的代码量，把动态规划的两个核心概念都塞进去了：状态定义和状态转移。你只要想明白dp[i]是以nums[i]结尾的最长递增子序列长度，转移方程几乎自己就出来了。

但它又能继续往下挖：当n来到十万级别，O(n^2)是肯定跑不过的，这时候需要换一个思路，用贪心维护一个“最小末尾值”数组，再配合二分查找把复杂度降到O(n log n)。

很多刷题的人只背了优化解法，却说不清为什么 tails 数组的长度就是答案。我建议你把两种解法都亲手写一遍，尤其是用同一个测试用例去逐步打印数组，你会直观看到“替换”比“追加”更聪明在哪。

2. 动态规划：O(n²) 的朴素但直观解法

2.1 dp 状态定义：以 nums[i] 结尾

动态规划的第一步永远是设计状态。LIS 里最常见的状态是：

dp[i] 表示以 nums[i] 作为最后一个元素的最长递增子序列长度。

为什么一定要“以 nums[i] 结尾”，而不直接定义成“前 i 个元素里的最长递增子序列长度”？

因为递增子序列能不能继续往后扩展，取决于当前最后一个元素的值。如果你只记录前 i 个元素的最大长度，那这个最大长度对应的结尾数字是多少？不知道。后面再来一个更大的数字，你也没办法判断能不能接上去。

举个例子，前三个元素是[5, 1, 2]，前两个元素的最长子序列是[5]，长度1，结尾是5；但前三个元素的最长子序列是[1, 2]，长度2，结尾是2。如果新来一个数字3，它能接到结尾2后面形成长度3，却接不到5后面。所以你光记一个“前 i 个最大长度”远远不够，必须把每个可能的结尾都记下来。

这就是“以 i 结尾”的真正原因：它把子序列的边界信息保留在状态里，保证后续转移时有据可依。这种设计在线性dp里非常常见，练熟这道题，后面很多字符串、区间 dp 都会用到类似套路。

2.2 状态转移方程与代码模板

状态转移其实就是在做一件事：枚举所有可能接在nums[i]前面的元素nums[j]，如果nums[j] < nums[i]，那么nums[i]可以接在以nums[j]结尾的子序列后面，长度就是dp[j] + 1。

初始情况下，每个元素自身可以单独构成一个长度为1的子序列，所以dp[i] = 1。

转移式可以写成：

dp[i] = max(dp[i], dp[j] + 1) 其中 0 <= j < i 且 nums[j] < nums[i]

完整代码：

from typing import List class Solution: def lengthOfLIS(self, nums: List[int]) -> int: if not nums: return 0 n = len(nums) dp = [1] * n for i in range(n): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)

最后返回的是max(dp)，不是dp[-1]。因为答案不一定是以最后一个元素结尾的子序列，比如[1, 3, 6, 7, 9, 4, 5, 6]，以最后一个6结尾的最长长度可能是4，但全局最长是5，结尾在9那里。

2.3 复杂度分析和几个容易忽略的细节

时间上是两层循环：

• 外层遍历 i，总共 n 个元素；
• 内层枚举 j 从 0 到 i-1，平均 n/2 次。

所以时间复杂度是O(n^2)，空间复杂度O(n)。这个复杂度在力扣原题的n <= 2500下足够通过，但一旦数据量到10^5级别就悬了。

写这段代码时有几个细节值得注意。

第一，内层循环必须遍历所有 j，而不是只看i-1。因为递增子序列可以跳过很多中间元素，nums[i]可能接在很前面的某个小数字后面。比如[2, 1, 3]，当 i=2 时，nums[2]=3，它不仅能接在1后面，也能接在2后面，两个都要比较。

第二，转移条件是nums[j] < nums[i]，等号不能算。如果数组里有大量重复元素，比如[2, 2, 2]，那么所有 j 都不满足严格小于，三个 dp 值都是1，最终结果就是1。

第三，dp[i]在循环过程中可能会被多次更新，所以用max来取最优。不能直接把dp[j] + 1赋值给dp[i]，因为可能后面枚举到更长的 j，也可能一个都不满足。

3. 贪心 + 二分：从 O(n²) 降到 O(n log n)

3.1 维护“最小末尾值”数组的贪心思想

这一小节是整个题解里最值得反复琢磨的部分。

我们先改变思路：不关心具体最长子序列长什么样，只关心“在长度固定时，能不能让它的末尾元素尽可能小”。末尾越小，后面能接的数字范围就越大，越有可能形成更长的子序列。这个思想说白了就是贪心：每一步都让当前状态的“潜力”最大化。

实现上维护一个数组tails：

tails[k] 表示长度为 k+1 的递增子序列中，最小的末尾元素值。

这里有个很关键的理解：tails数组本身不一定是真实存在的某个递增子序列，它只是记录“每个长度对应的最优秀末尾值”。我们只拿它的长度作为答案，不拿内容当真。

遍历每个x，做这样一件事：

• 如果x比tails里所有元素都大，说明它可以接到当前最长子序列后面，于是追加到末尾，最长长度加1；
• 否则，找到第一个大于等于x的位置，用x替换掉那个位置的值。

替换看起来有点“反悔”，因为本来某个位置已经有一个末尾值了，现在来了个更小的，就把原来那个赶走。这种“当前不是最优，就换一个更优的”思路，和信奥里常说的反悔贪心有异曲同工的感觉。

为什么替换不会破坏已有长度？因为替换只发生在长度不变的位置上，没有丢掉已经获得的长度，只是降低该长度的末尾值，让它对后续扩展更友好。

我习惯用扑克牌来理解这个操作：你有好几堆牌，每堆的堆顶记录了“当前这堆的最小顶牌”。新来一张牌，如果比所有堆顶都大，就新开一堆；否则放到第一张比它大的牌所在的那堆上，把原来的顶牌压下去。牌堆的数量就是最长递增子序列的长度。这个玩法有个正式的名字，叫耐心排序。

3.2 二分查找用 bisect_left 还是 bisect_right

因为tails是严格递增的，所以可以用二分查找加速。Python 里直接用bisect模块：

from bisect import bisect_left pos = bisect_left(tails, x)

这里必须用bisect_left，它返回第一个大于等于x的下标。如果数组允许非递减，例如让你求“最长非递减子序列”，那要改成bisect_right，它返回第一个大于x的下标，这样相同元素可以接在后面。

怎么快速记住？bisect_left会把相等的元素当作“可以替换”，所以最终序列里不会保留相等的两个值；bisect_right会把相等的元素当作“可以追加”，所以非递减场景用它。本题的“严格递增”对应bisect_left。

还有一个常见写法是：

if not tails or x > tails[-1]: tails.append(x) else: pos = bisect_left(tails, x) tails[pos] = x

这个写法是在做显式判断，逻辑上也完全没问题。但我个人更喜欢直接用bisect_left返回的位置判断：

pos = bisect_left(tails, x) if pos == len(tails): tails.append(x) else: tails[pos] = x

这样少一次额外比较，代码也更对称。

3.3 完整代码与模拟运行

完整代码如下：

from typing import List from bisect import bisect_left class Solution: def lengthOfLIS(self, nums: List[int]) -> int: tails = [] for x in nums: pos = bisect_left(tails, x) if pos == len(tails): tails.append(x) else: tails[pos] = x return len(tails)

用[10, 9, 2, 5, 3, 7, 101, 18]完整跑一遍，看看 tails 怎么变：

x=10: tails = [10] x=9: bisect_left([10], 9) = 0，替换 -> [9] x=2: bisect_left([9], 2) = 0，替换 -> [2] x=5: bisect_left([2], 5) = 1，末尾追加 -> [2, 5] x=3: bisect_left([2, 5], 3) = 1，替换 -> [2, 3] x=7: bisect_left([2, 3], 7) = 2，追加 -> [2, 3, 7] x=101: bisect_left([2, 3, 7], 101) = 3，追加 -> [2, 3, 7, 101] x=18: bisect_left([2, 3, 7, 101], 18) = 3，替换 -> [2, 3, 7, 18]

最后tails = [2, 3, 7, 18]，长度4，答案4。这里很巧合，tails本身也是一个真实的最长递增子序列，但后面我会告诉你，这个“巧合”不能被当成普遍规律。

4. 两种解法对比与适用场景

4.1 时间、空间、代码量对比

我把两种解法放在一张表里，方便你一眼看清差别：

如果你只是应付力扣原题，n <= 2500，两种都能过。但在面试回答时，我一般建议先用动态规划讲清楚状态，再说“如果数据量大，可以用贪心加二分优化到 O(n log n)”。这个回答过程本身就展示了你的思路层次。

4.2 能不能通过贪心数组重新构造出真实序列

很多人刷完题会有一个疑问：tails数组里存的不就是最长递增子序列吗？为什么很多题解说不能直接用？

问题出在替换操作上。tails里的每个元素只是“当前长度下的最小末尾值”，这些值来自不同历史阶段的元素，组合起来不一定保持在下标上递增，也不一定真的能形成一条合法的子序列。

举个反例：

nums = [3, 1, 2, 0, 4]

跑一遍贪心：

x=3: tails = [3] x=1: 替换 -> [1] x=2: 追加 -> [1, 2] x=0: 替换 -> [0, 2] x=4: 追加 -> [0, 2, 4]

最后tails = [0, 2, 4]，长度3，答案确实是3。但你在原数组里能找到[0, 2, 4]这个子序列吗？0的下标在2的后面，2的下标在4的前面，所以按照原数组顺序，[0, 2, 4]根本不是一个合法子序列。真实答案可以是[1, 2, 4]或[0, 4]再加一个凑长度，反正长度是3。

这就是为什么tails只配当“长度计数器”，不能当答案输出。如果你真的需要输出一个具体子序列，有两个办法：

• 用动态规划的状态转移，同时维护一个prev[i]数组，记录每个dp[i]是从哪个 j 转移过来的，最后倒序回溯；
• 用贪心的变体“耐心排序”，在替换时额外记录每个元素的前驱下标，最后从最后一堆的顶部开始回溯。

第一种写起来更直白，大多数面试场景已经够用：

def lis_with_path(nums): if not nums: return [] n = len(nums) dp = [1] * n prev = [-1] * n end = 0 for i in range(n): for j in range(i): if nums[j] < nums[i] and dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 prev[i] = j if dp[i] > dp[end]: end = i path = [] cur = end while cur != -1: path.append(nums[cur]) cur = prev[cur] return path[::-1]

注意prev[i]的更新要和dp[i]的更新同步，不能只比较大小忘了记录来源。而且如果出现多个 j 都能提供相同长度，任选一个即可，得到的子序列不一定唯一，但长度一定对。

4.3 什么时候该用哪种解法

我的选择标准很简单：

• 只要求最长长度，而且数组很长、数据量达到10^5以上，用贪心加二分；
• 题目要求输出具体的子序列，或者要求你给出所有可能长度的信息，优先用动态规划，因为它天然保留每个位置的状态；
• 如果是面试手撕代码，先写动态规划让面试官看到思路，再提优化，不要一上来就甩贪心二分，容易让人觉得你在背模板。

另外还有一种折中：你可以先写O(n^2)的 dp 验证思路，再写一个贪心二分的方法做对照，用随机数据对比两个结果是否一致。这是我很喜欢的自测方式，能快速发现自己对边界条件的理解有没有出问题。

5. 实战中容易踩的坑与调试技巧

5.1 空数组、单元素数组的边界处理

力扣原题数组长度至少为1，所以很多人会忽略空数组。但在本地测试、或者把代码改成工具函数时，空数组必须考虑。

• 动态规划写法里，如果nums为空，直接返回0，否则dp[0]会越界；
• 贪心写法天然支持空数组，因为tails为空，循环不执行，返回len(tails)就是0；
• 单元素数组两种写法都返回1，不会出错。

别小看这个边界，很多人在面试现场写 dp 时忘记判空，结果被测试用例打脸。养成习惯：拿到一个数组类题目，先问自己数组能不能为空，能的话就在入口处理掉。

5.2 重复元素对“严格递增”的影响

如果题目把“严格递增”换成“非递减”，整个解法的行为都会变。

看一个极端例子：

nums = [4, 4, 4, 4]

严格递增答案是1，因为任何两个4都不能构成递增关系。

如果用动态规划，转移条件是nums[j] < nums[i]，所有4之间都不满足，所以 dp 全是1。

如果用贪心加二分，并且正确使用bisect_left，第一个4会放到索引0，后面的4也都会bisect_left到索引0，然后不断替换，数组长度一直是1。

但如果你误用bisect_right，第二个4就会追加到后面，tails会变成[4, 4]，得到错误答案2。这是二分写法里最经典的翻车点。所以每次写完，都用一个全是相同数字的用例去测一下，能立刻暴露问题。

5.3 二分法下标越界和返回值的坑

bisect_left的返回值范围是[0, len(tails)]。返回len(tails)时说明x比 tails 中所有元素都大，应该追加；返回其他值时说明找到了第一个大于等于x的位置，用x替换。

新手容易在判断条件上犯错：

# 错误写法 if pos > len(tails): tails.append(x)

这永远不会成立，因为pos最多等于len(tails)，不会大于。正确写法是if pos == len(tails)。

还有一种常见写法是：

if x > tails[-1]: tails.append(x) else: tails[bisect_left(tails, x)] = x

这里要求使用前保证tails非空。如果tails为空，tails[-1]会直接抛异常，需要额外加判断。所以用我前面给的那种统一写法会更省心，不用管数组空不空。

5.4 调试技巧：打印 tails 和 dp

我刷这道题时最喜欢做的一件事，就是写一个辅助函数打印中间状态，特别是贪心解法：

def debug_lis(nums): tails = [] for i, x in enumerate(nums): pos = bisect_left(tails, x) if pos == len(tails): tails.append(x) else: tails[pos] = x print(f"i={i}, x={x}, tails={tails}") return len(tails)

这段输出能很直观地告诉你，哪个元素触发了替换，哪个元素触发了追加，也能让你快速发现为什么有些时候 tails 内容不是真实序列。

动态规划那边则可以打印dp数组，对照去看每一个位置的转移来源。比如[1, 3, 2, 4]的 dp 值会是[1, 2, 2, 3]，你能看到最后一个4可以接到多个位置后面，但最长的是接在1后面形成的长度3。

6. 延伸思考：从这道题到更多变体

6.1 最长递增子序列的常见变体

LIS 的原型很简单，但它的变体非常多，而且都是面试和竞赛里的常客。

第一类是“二维化”。比如力扣354题“俄罗斯套娃信封问题”，信封有宽和高，信封A能套进信封B需要宽、高都严格小于B。这个题要先按宽度升序、宽度相同时高度降序排序，然后对高度数组求 LIS。排序的目的就是把二维问题降成一维，再套用标准的 LIS。

第二类是“带权最值”。比如求“最大递增子序列和”，不是求最长长度，而是求递增子序列的最大元素和。这时候 dp 状态不再从1起跳，而是从nums[i]起跳：

dp[i] = nums[i] for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + nums[i])

第三类是“可相等”。比如求最长非递减子序列，只要把转移条件改成<=，贪心那边的二分也改成bisect_right即可。

还有更进阶的变体，比如二维平面上求最大递增链、在树或 DAG 上求最长路径，本质上都能回到 LIS 的状态设计思路上来。

6.2 贪心思想在周赛里有多常见

你可能在热词里看到过“反悔贪心”“周赛430”之类的说法。这类题目在周赛里频繁出现，其实不是偶然。

LIS 的贪心写法就是一种很朴素的“反悔模型”：我先把某个长度下的末尾值固定下来，后来遇到更小的合适值，就替换掉。它没有真的撤销之前所有决策，但通过替换不断修正局部最优，最终达到全局最优。

周赛里更复杂的反悔贪心，比如用优先队列维护一组候选，当遇到一个更优方案时，把队列里最差的元素弹出。这个思路和 LIS 贪心在精神上是同构的：维护一组“潜力最大的状态”，并随时准备用更好的替换它。

所以我建议你把 LIS 贪心解法理解透，而不是只背代码。当你真的理解的替换操作，后面遇到很多“维护当前最优集合”的题目，都会觉得眼熟。

在我自己的刷题习惯里，这道题最少要写三遍：第一遍用动态规划，把状态转移和边界条件搞清楚；第二遍用贪心加二分，重点理解tails数组的含义，并且用随机数据交叉验证两种解法的结果；第三遍对着白板讲给别人听，能讲清楚为什么tails不能直接当子序列输出，才算是真正过关。最长递增子序列就是这样一道题，代码可能不超过十行，但背后的状态设计、贪心选择、二分边界，每一层都值得你慢慢拆开看。