最长上升子序列(LIS)算法详解：从动态规划到贪心二分优化-开发者社区

1. 从怪盗基德的滑翔翼到最长上升子序列：一个经典模型的诞生

如果你看过《名侦探柯南》，一定对怪盗基德那身标志性的白色礼服和潇洒的滑翔翼印象深刻。他总能从高楼一跃而下，借助气流在城市上空穿梭，选择最合适的路线逃脱或接近目标。这个场景，如果抽象成一个算法问题，就成了“怪盗基德的滑翔翼”这道经典的动态规划入门题。题目大意是：给定一排不同高度的楼房，怪盗基德可以选择一个起点，然后只能向一个方向（左或右）单调下降地跳跃到更矮的楼顶，问他最多能经过多少栋楼？这本质上，就是求一个序列的最长下降子序列。而它的孪生兄弟——最长上升子序列，则是算法世界里一个更为基础、应用也更为广泛的模型。

最长上升子序列，简称LIS，它的定义简单得令人发指：在一个给定的数值序列中，找到一个最长的子序列，使得这个子序列的元素是严格递增的。比如序列[10, 9, 2, 5, 3, 7, 101, 18]，它的一个最长上升子序列是[2, 5, 7, 101]，长度为4。别看定义简单，LIS模型是连接离散数学、动态规划、贪心算法乃至数据结构的绝佳桥梁，是信息学竞赛和算法面试中经久不衰的考点。从判断股票的最长上涨趋势，到安排会议的最优日程，再到计算最长递增的文件版本链，其思想无处不在。

很多人初学动态规划时，会被各种状态定义和转移方程搞得晕头转向。LIS模型就像一个完美的“教学案例”，它状态定义直观（以某个元素结尾的LIS长度），转移方程清晰（向前找所有比自己小的元素），完美诠释了动态规划“最优子结构”和“无后效性”的核心思想。理解透了LIS，很多更复杂的线性DP问题都能触类旁通。今天，我们就抛开怪盗基德的华丽外壳，深入这个模型的内部，不仅搞懂如何求出长度，还要掌握如何输出具体序列，并探讨其高效的优化算法。

2. 动态规划解法：最直观的思维方式与实现细节

当我们拿到一个序列，比如arr = [3, 1, 4, 1, 5, 9, 2, 6]，要求它的LIS长度时，最符合人类直觉的想法就是动态规划。这种思路的核心在于分解问题：我不直接求整个序列的LIS，而是先解决一系列更小的子问题。

2.1 状态定义与转移方程的推导

我们定义dp[i]表示以第i个元素（arr[i]）为结尾的最长上升子序列的长度。注意这个定义的关键词“以...为结尾”，它保证了我们考虑的子序列一定会包含arr[i]这个元素。为什么要这么定义？因为这样具有“无后效性”——dp[i]的值只依赖于i之前那些比arr[i]小的元素的dp值，而不会受到i之后元素的影响。

那么dp[i]怎么求呢？既然子序列必须以arr[i]结尾，那么arr[i]的前一个元素（如果存在的话）一定是序列中在i之前、且比arr[i]小的某个元素arr[j]（j < i且arr[j] < arr[i]）。所以，我们需要遍历i之前的所有位置j，如果arr[j] < arr[i]，那么arr[i]就可以接在arr[j]结尾的子序列后面，形成一个新的、更长的上升子序列，其长度就是dp[j] + 1。

我们要找的是最长的那个，所以dp[i]应该取所有可能情况中的最大值。如果i之前没有比arr[i]小的元素，那么以arr[i]结尾的LIS就是它自己，长度为1。由此，我们得到状态转移方程：

dp[i] = max(dp[j]) + 1, 对于所有 j < i 且 arr[j] < arr[i]dp[i]的初始值至少为1（每个元素自身构成一个长度为1的上升子序列）。

以arr = [3, 1, 4, 1, 5, 9, 2, 6]为例，我们手动计算一下：

i=0, arr[0]=3: 前面没有元素，dp[0]=1
i=1, arr[1]=1: 前面元素3比1大，不满足上升条件，dp[1]=1
i=2, arr[2]=4: 前面比4小的有3和1，dp[0]=1,dp[1]=1，最大值是1，所以dp[2]=1+1=2（序列[3,4]或[1,4]）
i=3, arr[3]=1: 前面没有比1小的，dp[3]=1
i=4, arr[4]=5: 前面比5小的有3,1,4,1。对应的dp值为1,1,2,1，最大值是2，所以dp[4]=2+1=3（例如序列[1,4,5]）
i=5, arr[5]=9: 前面所有元素都比9小，找最大的dp值，是dp[4]=3，所以dp[5]=3+1=4（例如序列[1,4,5,9]）
i=6, arr[6]=2: 前面比2小的只有1（arr[1]和arr[3]），dp值都是1，所以dp[6]=1+1=2（序列[1,2]）
i=7, arr[7]=6: 前面比6小的有3,1,4,1,5,2。对应的dp值为1,1,2,1,3,2，最大值是3，所以dp[7]=3+1=4（例如序列[1,4,5,6]）

最终，整个序列的LIS长度就是所有dp[i]中的最大值，即max(dp)=4。

2.2 代码实现与逆向追踪输出具体序列

基于上面的推导，代码实现非常直接。这里以Python为例：

def length_of_lis_dp(nums): if not nums: return 0 n = len(nums) dp = [1] * n # 初始化dp数组，每个位置至少长度为1 max_length = 1 for i in range(n): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) max_length = max(max_length, dp[i]) return max_length # 测试 arr = [3, 1, 4, 1, 5, 9, 2, 6] print(length_of_lis_dp(arr)) # 输出: 4

这段代码的时间复杂度是 O(n²)，因为对于每个i，我们都要遍历它之前所有的j。空间复杂度是 O(n)，用于存储dp数组。

注意：这里求出的只是长度。在很多实际场景中，我们不仅需要知道长度，还需要知道这个最长的子序列具体是什么。这就需要用到“逆向追踪”的技巧。

逆向追踪的思路是：我们先找到dp值最大的那个位置i（即LIS的最后一个元素）。然后，我们从i开始向前找，寻找一个位置j（j < i），它需要满足两个条件：1.arr[j] < arr[i]；2.dp[j] == dp[i] - 1。这第二个条件至关重要，它意味着arr[j]正好是arr[i]在LIS中的前一个元素。重复这个过程，直到我们找到一个dp值为1的元素，就完成了整个序列的构建。

def get_lis_sequence(nums): if not nums: return [] n = len(nums) dp = [1] * n # 额外记录前驱节点，用于回溯 prev = [-1] * n 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 # 记录i是从哪个j转移过来的 # 找到dp最大值的位置 max_len = max(dp) end_pos = dp.index(max_len) # 逆向构建序列 lis_seq = [] while end_pos != -1: lis_seq.append(nums[end_pos]) end_pos = prev[end_pos] lis_seq.reverse() # 因为我们是从后往前加的，需要反转 return lis_seq # 测试 arr = [3, 1, 4, 1, 5, 9, 2, 6] print(get_lis_sequence(arr)) # 输出可能是 [1, 4, 5, 9] 或 [1, 4, 5, 6]

这里有一个细节：对于一个序列，LIS可能不唯一（比如上面的例子，[1,4,5,9]和[1,4,5,6]都是长度为4的LIS）。我们的回溯方法通常找到的是最先达到最大长度的那个序列。如果你需要所有LIS，回溯会稍微复杂一些，需要记录所有可能的前驱。

2.3 动态规划解法的局限性分析

O(n²) 的时间复杂度在n较大时（比如超过10^4）就会成为性能瓶颈。这是由我们“向前遍历所有可能”的暴力搜索方式决定的。有没有办法优化呢？仔细观察状态转移过程，我们其实是在为每个arr[i]寻找它前面所有比它小的元素中，dp值最大的那个。这本质上是一个“在动态变化的数据集中查询最大值”的问题。我们能否维护一个更高效的数据结构来加速这个查询？这就引出了基于贪心+二分的优化算法。

3. 贪心+二分优化：将复杂度降至O(n log n)

动态规划解法慢，是因为内层循环是线性的。优化的核心思想是：我们不再关心以每个元素结尾的具体LIS长度，而是关心对于某个固定的长度L，所有长度为L的上升子序列中，结尾元素最小可以是多少。这个结尾元素越小，未来接上其他元素、构成更长序列的潜力就越大。

3.1 维护“最小结尾数组”的核心思想

我们定义一个数组tails。tails[i]存储的是所有长度为 i+1 的上升子序列中，结尾元素的最小值。这个数组有一个非常重要的性质：它一定是严格递增的。

为什么？可以用反证法。假设存在tails[i] >= tails[j]且i < j。tails[j]是某个长度为 j+1 的上升子序列的结尾，那么这个序列的前 j 个元素必然构成一个长度为 j 的上升子序列，并且它的结尾元素一定小于tails[j]，因此也小于等于tails[i]。这意味着存在一个长度为 j 的上升子序列，其结尾元素小于等于tails[i]，这与tails[i]是长度为 i+1 的上升子序列的最小结尾值相矛盾。所以tails数组必须递增。

有了这个递增的性质，事情就简单了。当我们遍历原数组nums的每个元素x时：

如果x比tails中所有元素都大，说明我们可以延长当前最长的上升子序列。那么就把x追加到tails末尾，表示我们发现了一个更长的LIS，其最小结尾是x。
否则，我们就在tails数组中寻找第一个大于等于x的元素，并用x替换它。这一步非常关键，它是在“同等长度下，用一个更小的结尾元素去替换原来的结尾元素”，为未来可能接上更大的数创造了更好的条件。

因为tails数组是递增的，所以第二步“寻找第一个大于等于x的元素”可以用二分查找在 O(log n) 时间内完成。

3.2 算法步骤详解与模拟推演

让我们用之前的例子arr = [3, 1, 4, 1, 5, 9, 2, 6]来模拟这个过程：

初始化tails为空数组[]。
遍历arr[0]=3:
- tails为空，直接加入。tails = [3]。这表示长度为1的LIS，最小结尾是3。
遍历arr[1]=1:
- 在tails=[3]中二分查找第一个 >=1 的元素，找到tails[0]=3。
- 用1替换3。tails = [1]。这表示长度为1的LIS，最小结尾可以优化为1（比3更好）。
遍历arr[2]=4:
- tails=[1]，4比所有元素都大，追加到末尾。tails = [1, 4]。这表示长度为1的LIS最小结尾是1，长度为2的LIS最小结尾是4。
遍历arr[3]=1:
- 在tails=[1,4]中二分查找第一个 >=1 的元素，找到tails[0]=1。
- 1等于1，替换后不变。tails = [1, 4]。这一步看似没变，但逻辑上是正确的。
遍历arr[4]=5:
- tails=[1,4]，5比所有元素都大，追加。tails = [1, 4, 5]。现在有了长度为3的LIS。
遍历arr[5]=9:
- 比所有元素都大，追加。tails = [1, 4, 5, 9]。长度为4的LIS出现。
遍历arr[6]=2:
- 在tails=[1,4,5,9]中二分查找第一个 >=2 的元素，找到tails[1]=4。
- 用2替换4。tails = [1, 2, 5, 9]。注意，这个替换非常精妙。它并没有破坏“长度为2的LIS最小结尾是2”这个事实（序列[1,2]），并且让tails[2]=5的未来潜力更大了（因为现在结尾是2，更容易接上比5稍小但大于2的数）。
遍历arr[7]=6:
- 在tails=[1,2,5,9]中二分查找第一个 >=6 的元素，找到tails[3]=9。
- 用6替换9。tails = [1, 2, 5, 6]。

遍历结束。最终tails数组的长度是4，这就是LIS的长度。但是请注意，此时的tails数组[1, 2, 5, 6]并不一定是一个真实的、存在于原序列中的上升子序列！它只是记录了各个长度下的最小结尾值。例如，在原序列中，2出现在5之后，[1,2,5,6]并不是一个合法的子序列。tails数组是贪心策略下的一种“潜力记录”，它只保证长度是正确的。

3.3 代码实现与正确性理解

import bisect def length_of_lis_greedy(nums): if not nums: return 0 tails = [] for num in nums: # 使用bisect_left找到第一个 >= num 的位置 pos = bisect.bisect_left(tails, num) if pos == len(tails): tails.append(num) # num比所有结尾都大，延长LIS else: tails[pos] = num # 替换，保持最小结尾性质 return len(tails) # 测试 arr = [3, 1, 4, 1, 5, 9, 2, 6] print(length_of_lis_greedy(arr)) # 输出: 4

这段代码的时间复杂度是 O(n log n)，空间复杂度是 O(n)。bisect.bisect_left是Python标准库中高效的二分查找函数。

理解这个算法的关键在于，tails数组维护的是一种“可能性”。替换操作（tails[pos] = num）并不会改变当前已发现的LIS长度，但它优化了未来扩展的可能性。最终tails的长度就是全局最优的LIS长度。这个算法无法直接输出具体的LIS序列，因为它丢失了元素之间的顺序信息。如果需要输出序列，通常还是需要结合动态规划的回溯方法，或者使用更复杂的记录方式。

4. 模型扩展、常见变体与实战应用场景

掌握了标准的LIS模型后，我们来看看它的一些变体和实际应用。这能帮助你真正理解这个模型的灵活性。

4.1 非严格递增与最长不下降子序列

标准LIS要求“严格递增”（arr[j] < arr[i]）。如果问题变成“最长不下降子序列”（允许相等），我们只需要在动态规划的状态转移条件中，将<改为<=即可。

def length_of_longest_non_decreasing_subsequence(nums): 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)

在贪心+二分算法中，当遇到相等元素时，策略需要微调。对于“不下降”序列，我们应该替换的是tails中第一个大于num的元素（bisect.bisect_right），而不是“大于等于”。因为允许相等，所以当num等于tails中某个值时，我们不应该替换它，替换了也不会让结尾变得更小，反而可能破坏序列的合法性。但更常见的简化做法是，在二分查找时仍然使用bisect_left，因为对于允许相等的序列，用相等的数替换相等的数，结果是一样的。不过，严格来说，对于tails数组的定义需要调整为“长度为 i+1 的不下降子序列的最小结尾值”，其单调性变为非严格递增。

4.2 二维偏序问题：俄罗斯套娃信封

这是一个经典的LIS变体问题（LeetCode 354）。给你一堆信封的宽度和高度(w, h)，如果一个信封的宽度和高度都大于另一个信封，那么它可以套进去。问你最多能套多少层？

这个问题可以巧妙地转化为LIS。首先，我们将所有信封按宽度w升序排序。但是，如果宽度相同怎么办？如果宽度相同，我们必须按高度h降序排序。为什么？考虑两个信封(w, h1)和(w, h2)，h1 < h2。如果我们按高度升序排，那么在寻找高度LIS时，(w, h1)和(w, h2)可能会被同时选中（因为h1 < h2），但这违反了宽度必须严格递增的条件（因为宽度w相同）。按高度降序排序后，对于相同宽度的信封，高度大的在前，这样在后续求高度的LIS时，它们就不会被同时选中（因为高度是递减的，不满足上升条件）。

排序之后，问题就变成了：在排序后的高度数组h[]上，求严格递增子序列的最大长度。因为宽度已经通过排序保证了非递减，而高度严格递增则保证了宽度也一定是严格递增的（对于宽度相同的信封，其高度是降序的，不可能同时被选入一个上升序列）。

def max_envelopes(envelopes): if not envelopes: return 0 # 排序：宽度升序，高度降序 envelopes.sort(key=lambda x: (x[0], -x[1])) # 提取高度序列 heights = [h for _, h in envelopes] # 在高度序列上求LIS（严格递增） return length_of_lis_greedy(heights) # 使用之前的贪心二分函数

这个例子展示了LIS模型处理二维偏序问题的强大能力：通过巧妙的排序，将二维比较降维到一维的序列问题。

4.3 输出所有最长上升子序列

有时候，我们需要输出所有可能的LIS，而不仅仅是其中一个。这比输出一个要复杂。动态规划方法可以做到，但需要记录所有可能的前驱节点。

思路是：在计算dp数组时，对于每个位置i，我们不仅记录最长长度dp[i]，还用一个列表pre[i]来记录所有能转移到i的前驱位置j（满足j < i,arr[j] < arr[i]且dp[j] + 1 == dp[i]）。计算完所有dp后，我们找到所有dp值等于最大长度max_len的位置，这些位置就是所有LIS的终点。然后从每个终点开始，通过pre数组进行深度优先搜索（DFS）回溯，就能构造出所有路径。

def find_all_lis(nums): if not nums: return [] n = len(nums) dp = [1] * n pre = [[] for _ in range(n)] # 记录所有前驱 max_len = 1 for i in range(n): for j in range(i): if nums[j] < nums[i]: if dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 pre[i] = [j] # 发现更优长度，清空前驱，只记录j elif dp[j] + 1 == dp[i]: pre[i].append(j) # 同等长度的前驱，追加记录 max_len = max(max_len, dp[i]) # 找到所有终点 ends = [i for i in range(n) if dp[i] == max_len] result = [] def dfs(pos, path): path.append(nums[pos]) if not pre[pos]: # 没有前驱，说明到达起点 result.append(path[::-1]) # 路径是反向添加的，需要反转 else: for p in pre[pos]: dfs(p, path.copy()) # 注意要传递path的副本 path.pop() for end in ends: dfs(end, []) return result # 测试 arr = [1, 3, 5, 4, 7] print(find_all_lis(arr)) # 输出: [[1, 3, 4, 7], [1, 3, 5, 7]]

这种方法在序列长度不大时可行，但当LIS数量很多时（最坏情况是指数级），输出所有序列是不现实的。通常题目只会要求输出一个或长度。

4.4 实际应用场景举例

LIS模型的应用远不止于做题：

金融分析：分析一只股票价格的历史序列，最长上涨天数或最长连续上涨趋势的长度，可以帮助判断股票的某种“动量”或“韧性”。
项目调度：有一系列任务，每个任务有开始时间和结束时间，且必须按某个顺序进行（例如，结束时间早的必须先做）。如果任务序列按开始时间排序后，其结束时间的最长上升子序列，可能对应着能按顺序完成的最多任务数（这是一个简化模型，实际调度问题更复杂）。
文件版本管理：想象一个文件被多次修改保存，每个版本有一个时间戳和内容哈希。如果你只想保留那些“内容发生实质性变化”的版本（即哈希值不同的版本），并且希望按时间顺序保留一个最长的版本链，这也可以抽象为一个LIS问题（对时间戳序列，根据哈希值是否相同来决定“上升”条件）。
生物信息学：在DNA或蛋白质序列比对中，寻找最长公共子序列（LCS）是核心问题，而LIS可以看作是LCS在特定条件下的特例或子问题。

5. 算法选择、边界条件与调试技巧

在实际编码和面试中，除了理解算法原理，如何选择、实现以及调试同样重要。

5.1 何时用DP，何时用贪心二分？

这是一个很实际的问题。我的选择标准通常如下：

首选贪心二分法（O(n log n)）：在99%的情况下，特别是当n可能很大（>1000）时，都应该使用它。它的效率高，代码简洁。
使用动态规划（O(n²)）的情况：
1. 需要输出具体的LIS序列，而不仅仅是长度。贪心二分法丢失了序列信息，虽然可以通过更复杂的记录方式找回，但DP回溯更直观。
2. 问题变体无法直接应用贪心二分策略。例如，当“上升”的条件不是一个简单的数值大小时（比如需要满足一个复杂的谓词函数），DP的通用性更强。
3. 数据规模非常小，比如n <= 100，两种方法没有显著差异，DP更容易理解和实现。
4. 作为教学演示，DP更能揭示问题的最优子结构。

5.2 边界条件与特殊输入处理

健壮的代码必须考虑边界：

空序列：输入数组可能为None或[]，此时LIS长度为0。这是最容易忽略的边界，务必在函数开头判断。
单元素序列：长度为1，结果就是1。
全递减序列：如[5,4,3,2,1]，LIS长度为1。
全相等序列：如[2,2,2,2]，对于严格递增LIS，长度为1；对于非严格递增（不下降），长度为4。
包含重复元素的序列：对于严格递增LIS，重复元素不会同时被选中。在DP中，arr[j] < arr[i]确保了这一点。在贪心二分中，bisect_left在遇到相等元素时会返回其左侧位置，从而用新值替换旧值，保证了tails中元素的唯一性（对于严格递增）。

5.3 调试与验证：如何确保你的算法是对的？

当你写完代码，尤其是贪心二分这种有点“反直觉”的算法后，如何验证？

小数据暴力对比：写一个DP解法作为“暴力标准答案”。然后生成大量随机的小规模数组（比如长度10以内），分别用DP和你的优化算法计算长度，对比结果是否一致。这是最有效的验证方法。
打印中间状态：对于贪心二分，在循环中打印每一步更新后的tails数组。对照我们前面手动模拟的过程，看是否一致。这能帮你理解算法的动态过程。
测试变体：用同一套代码测试严格递增和非严格递增的变体，确保条件修改正确。
复杂度分析：确认你的二分查找是否正确。在Python中，使用bisect模块是稳妥的。如果自己实现二分，要小心边界条件（left,right的初始值和更新规则），这是二分法最容易出错的地方。

我自己在实现贪心二分时，就曾因为二分查找写错，导致结果偏大或偏小。后来养成了习惯：对于任何二分查找，先用几个简单例子在脑子里或纸上跑一遍，确认循环不变式。

5.4 一个综合案例：解决“怪盗基德的滑翔翼”

回到我们最初的标题。题目描述通常是：有N座建筑，给出它们的高度H。怪盗基德可以从任意建筑开始，选择向左或向右，但只能滑向高度递减的建筑。求他最多能经过的建筑数。

这其实就是求序列的最长下降子序列，但方向可以是左或右。一个巧妙的解法是：

分别求一遍从左到右的最长下降子序列（相当于对每个位置，求其左边能有多少更低的建筑）。
再求一遍从右到左的最长下降子序列（相当于对每个位置，求其右边能有多少更低的建筑）。
对于每个位置i，他可以以该建筑为起点，向左或向右滑。那么以i为起点的最大经过数就是max(left[i], right[i])，其中left[i]和right[i]分别是步骤1和2中求出的以i为结尾的最长下降子序列长度（注意方向）。
最终的答案就是所有位置这个最大值中的最大值。

这里“下降”就是LIS中“上升”的反义词。我们只需把状态转移条件中的<改为>即可。计算left数组时，正序遍历；计算right数组时，逆序遍历。

def kaito_kid_building(heights): n = len(heights) if n == 0: return 0 left = [1] * n # 从左向右，以i结尾的最长下降子序列 right = [1] * n # 从右向左，以i结尾的最长下降子序列 # 计算向左滑（正序，找前面更高的） for i in range(n): for j in range(i): if heights[j] > heights[i]: # 注意是下降，所以前面要比后面高 left[i] = max(left[i], left[j] + 1) # 计算向右滑（逆序，找后面更高的） for i in range(n-1, -1, -1): for j in range(i+1, n): if heights[j] > heights[i]: # 逆序遍历时，j在i后面，需要 heights[j] > heights[i] right[i] = max(right[i], right[j] + 1) max_buildings = 0 for i in range(n): # 以i为起点，可以选择向左或向右，取最大值 max_buildings = max(max_buildings, left[i], right[i]) return max_buildings # 测试 heights = [300, 207, 155, 300, 299, 170, 158, 65] print(kaito_kid_building(heights)) # 输出应为 6

这个例子展示了如何将LIS模型灵活应用于具体问题。理解模型的核心思想（状态定义、转移方程）比死记硬背代码更重要。当你遇到“最长上升/下降子序列”这类描述时，要能立刻联想到这个模型，并分析出具体是哪种变体（严格/非严格，单向/双向等）。