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]为例我们手动计算一下i0, arr[0]3: 前面没有元素dp[0]1i1, arr[1]1: 前面元素3比1大不满足上升条件dp[1]1i2, arr[2]4: 前面比4小的有3和1dp[0]1,dp[1]1最大值是1所以dp[2]112序列[3,4]或[1,4]i3, arr[3]1: 前面没有比1小的dp[3]1i4, arr[4]5: 前面比5小的有3,1,4,1。对应的dp值为1,1,2,1最大值是2所以dp[4]213例如序列[1,4,5]i5, arr[5]9: 前面所有元素都比9小找最大的dp值是dp[4]3所以dp[5]314例如序列[1,4,5,9]i6, arr[6]2: 前面比2小的只有1arr[1]和arr[3]dp值都是1所以dp[6]112序列[1,2]i7, arr[7]6: 前面比6小的有3,1,4,1,5,2。对应的dp值为1,1,2,1,3,2最大值是3所以dp[7]314例如序列[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开始向前找寻找一个位置jj 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]存储的是所有长度为 i1 的上升子序列中结尾元素的最小值。这个数组有一个非常重要的性质它一定是严格递增的。为什么可以用反证法。假设存在tails[i] tails[j]且i j。tails[j]是某个长度为 j1 的上升子序列的结尾那么这个序列的前 j 个元素必然构成一个长度为 j 的上升子序列并且它的结尾元素一定小于tails[j]因此也小于等于tails[i]。这意味着存在一个长度为 j 的上升子序列其结尾元素小于等于tails[i]这与tails[i]是长度为 i1 的上升子序列的最小结尾值相矛盾。所以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数组的定义需要调整为“长度为 i1 的不下降子序列的最小结尾值”其单调性变为非严格递增。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(keylambda 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²)的情况需要输出具体的LIS序列而不仅仅是长度。贪心二分法丢失了序列信息虽然可以通过更复杂的记录方式找回但DP回溯更直观。问题变体无法直接应用贪心二分策略。例如当“上升”的条件不是一个简单的数值大小时比如需要满足一个复杂的谓词函数DP的通用性更强。数据规模非常小比如n 100两种方法没有显著差异DP更容易理解和实现。作为教学演示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(i1, 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模型灵活应用于具体问题。理解模型的核心思想状态定义、转移方程比死记硬背代码更重要。当你遇到“最长上升/下降子序列”这类描述时要能立刻联想到这个模型并分析出具体是哪种变体严格/非严格单向/双向等。