1. 问题引入从“最长上升子序列”说起如果你刷过一些算法题或者正准备入门动态规划那么“最长上升子序列”Longest Increasing Subsequence, LIS绝对是一个绕不开的经典问题。我第一次遇到它时感觉题目描述很简单给定一个整数序列找出其中最长的、严格递增的子序列的长度。比如序列[10, 9, 2, 5, 3, 7, 101, 18]它的一个最长上升子序列是[2, 5, 7, 101]长度是4。看起来不难对吧但当你真正动手去实现尤其是想找到一个高效比如 O(n log n)的解法时就会发现里面藏着不少精巧的设计和容易踩的坑。洛谷的这道 B3637 题就是一个非常典型的练习场。这道题的价值在于它不仅仅是让你求出一个长度更是动态规划思想从入门到进阶的一块重要跳板。很多更复杂的问题比如“最大子数组和”、“最长公共子序列”甚至是某些字符串匹配、序列比对问题其核心思想都能在这里找到影子。更重要的是理解 LIS 的两种主流解法——经典的 O(n²) 动态规划和优化的 O(n log n) 贪心二分查找法——能极大地提升你对“状态定义”和“状态转移”的敏感度。今天我就结合自己多次实现和教学的经验把这道题的里里外外、前因后果以及那些教程里不常提的细节和坑点一次性给你讲透。2. 理解问题本质与核心概念拆解在动手写代码之前我们必须把问题本身和涉及到的概念彻底嚼碎。很多人算法写不好第一步就输在了对问题的理解上。2.1 什么是“子序列”和“子串”有什么区别这是第一个关键点也是新手最容易混淆的地方。子序列Subsequence和子串Substring有本质区别。子串必须是原序列中连续的一段。例如在字符串abcde中bcd是一个子串。子序列是从原序列中按顺序取出一些元素可以不连续但保持其原有的相对顺序。例如在序列[1, 5, 3, 4, 2]中[1, 3, 4]就是一个子序列跳过了5和2但它不是子串因为元素在原序列中不连续。对于 LIS 问题我们寻找的是“子序列”这意味着我们可以“跳过”中间那些不符合递增条件的元素从而可能找到更长的递增序列。这个“可以不连续”的特性是动态规划解法能够成立的前提因为它允许我们基于之前所有位置的状态来推导当前状态。2.2 “上升”的定义严格递增题目中的“上升”通常指的是严格递增Strictly Increasing即对于子序列中的任意两个相邻元素a[i]和a[j]i j都必须满足a[i] a[j]。注意这里没有等号。有些变体问题可能是“非递减”允许相等但洛谷 B3637 是标准的严格递增。这一点在写状态转移方程的比较条件时至关重要用还是会直接导致结果错误。2.3 输入输出与数据范围分析以洛谷 B3637 为例典型的输入格式是 第一行一个整数n代表序列长度。 第二行n个整数代表序列本身。 我们需要输出一个整数即最长上升子序列的长度。数据范围是关键中的关键它直接决定了你采用哪种算法能通过。如果n 1000或n 5000那么 O(n²) 的动态规划解法通常是够用的代码简单易于理解。如果n达到10^5甚至更大O(n²) 的复杂度可能达到10^10次操作必定会超时TLE。这时就必须使用 O(n log n) 的优化解法。理解数据范围并选择对应算法是算法竞赛和工程实践中一项非常重要的能力。拿到题目先看数据范围再决定思路这是一个好习惯。3. 基础解法O(n²) 动态规划详解这是理解 LIS 问题最直观、最符合动态规划教学路径的解法。我们先不追求极致效率而是把“状态”和“转移”这两个核心概念搞清楚。3.1 状态定义dp[i]到底代表什么定义状态是动态规划的第一步也是最容易出错的一步。对于 LIS一个最自然的状态定义是dp[i]表示以第i个元素下标 i注意我们通常从0或1开始计数为结尾的、所有上升子序列中最长的那个的长度。这里有几个要点以nums[i]结尾这是一个限制条件。我们最终要求的答案是整个序列的 LIS 长度它可能不以某个特定的i结尾。所以我们的答案将是所有dp[i]中的最大值即max(dp[0], dp[1], ..., dp[n-1])。“最长的那个”对于固定的结尾nums[i]可能有多种方式从前面的元素跳过来形成上升子序列。dp[i]要存储的是这些可能中的最大值。例如对于序列nums [1, 5, 3, 4, 2]dp[0]以1结尾只有它自己长度为1。dp[1]以5结尾。可以接在1后面形成[1,5]长度为2。所以dp[1] 2。dp[2]以3结尾。可以接在1后面形成[1,3]长度为2。它不能接在5后面因为5 3不满足上升。所以dp[2] 2。dp[3]以4结尾。可以接在1后面 ([1,4]长度2)也可以接在3后面 ([1,3,4]长度3)。显然[1,3,4]更长所以dp[3] 3。dp[4]以2结尾。只能接在1后面 ([1,2]长度2)。所以dp[4] 2。 最终所有dp[i]的最大值是dp[3] 3对应的 LIS 是[1,3,4]。3.2 状态转移方程推导现在我们知道了dp[i]的含义那么如何计算它呢也就是dp[i]和之前的dp[j]j i有什么关系思考过程要形成以nums[i]结尾的上升子序列那么序列的倒数第二个元素nums[j]必须满足两个条件j i在i之前。nums[j] nums[i]满足严格递增。在所有满足条件的j中我们选择那个能使得以nums[j]结尾的子序列最长的那个然后接上nums[i]。因为dp[j]本身就代表了以nums[j]结尾的最长长度所以接上nums[i]后新的长度就是dp[j] 1。因此状态转移方程为dp[i] max(dp[j] 1)其中j满足0 j i且nums[j] nums[i]。如果对于当前的i找不到任何一个满足nums[j] nums[i]的j怎么办这意味着nums[i]比前面所有数都小或者它是第一个数那么以它结尾的最长上升子序列就只能包含它自己长度为1。所以我们需要给dp[i]一个初始值。初始条件对于任何一个位置i最短的以它结尾的上升子序列就是它自身所以dp[i]的初始值至少为 1。我们可以将整个dp数组初始化为1。3.3 完整代码实现与逐行解析下面是用 Python 实现的 O(n²) 动态规划解法我会加上详细注释。def length_of_lis_n2(nums): 计算最长上升子序列的长度 (O(n^2) DP解法) :param nums: List[int] 整数序列 :return: int 最长上升子序列的长度 if not nums: # 边界条件空序列 return 0 n len(nums) # 1. 定义dp数组并初始化 # dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度 dp [1] * n # 初始化为1因为每个元素自身至少可以构成一个长度为1的子序列 # 2. 动态规划填表过程 for i in range(n): # 遍历每一个元素作为子序列的结尾 for j in range(i): # 遍历 i 之前的所有元素寻找可以接在后面的 if nums[j] nums[i]: # 必须满足严格递增条件 # 状态转移如果接在 nums[j] 后面能形成更长的序列则更新 dp[i] dp[i] max(dp[i], dp[j] 1) # 3. 最终结果不是 dp[n-1]而是 dp 数组中的最大值 # 因为最长上升子序列不一定以最后一个元素结尾 return max(dp) # 示例 nums [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis_n2(nums)) # 输出4关键点与易错点分析dp数组初始化dp [1] * n这行代码很简洁地完成了初始化。确保你理解为什么是1。内层循环j的范围for j in range(i)这意味着j从 0 遍历到i-1。这是正确的因为我们要找i之前的所有位置。状态转移的条件nums[j] nums[i]这里的确保了严格递增。如果是非递减允许相等则应改为。状态转移操作dp[i] max(dp[i], dp[j] 1)注意这里是max因为我们可能从多个不同的j转移过来要取能获得最大长度的那个。dp[i]的初始值是1在内层循环中可能会被多次更新变大。最终返回值return max(dp)。这是新手常犯的错误误以为答案是dp[n-1]。一定要记住LIS 可能出现在序列的任意位置结尾。复杂度分析时间复杂度O(n²)。外层循环n次内层循环平均n/2次嵌套后是平方级。空间复杂度O(n)用于存储dp数组。这个解法在n较小时比如几千完全可行代码清晰是理解动态规划解决 LIS 的基石。但当n很大时我们必须寻找更优的解法。4. 高效解法O(n log n) 贪心二分查找原理剖析当数据量变大O(n²) 无法承受时我们就需要利用 LIS 问题的特殊性质进行优化。O(n log n) 的解法非常巧妙它结合了贪心思想和二分查找。4.1 核心思想让上升子序列“长得更慢”我们换一个角度思考。假设我们想要一个尽可能长的上升子序列那么我们希望这个序列在保证递增的前提下每个位置上的数尽可能小。因为末尾的数越小后面就有更大的机会接上新的、更大的数从而使序列变得更长。我们维护一个数组tails。tails[i]的定义是所有长度为i1的上升子序列中末尾元素的最小值。为什么是i1因为数组下标通常从0开始tails[0]就代表长度为1的LIS的最小末尾。这个数组有一个重要性质它一定是严格递增的。证明假设tails[i]和tails[j]且i j。tails[j]是某个长度为j1的LIS的末尾这个序列的前i1个元素构成了一个长度为i1的上升子序列其末尾元素必然小于等于tails[j]因为是子序列而tails[i]是所有这种子序列末尾的最小值所以有tails[i] tails[j]严格递增。4.2 算法流程与二分查找的运用我们遍历原序列nums中的每个数x然后去更新tails数组。更新规则如下如果x比tails中所有元素都大说明我们找到了一个更长的上升子序列就将x添加到tails的末尾。此时tails的长度增加了1。否则我们在tails数组中找到第一个大于等于x的元素并用x替换它。因为tails数组是递增的所以我们可以用二分查找来高效地O(log n)找到这个位置。为什么可以替换替换操作不会改变tails数组的长度即当前找到的LIS长度但它让某个长度的上升子序列的末尾元素变得更小了用x替换了一个更大的数这为后续接上更大的数以延长序列创造了更好的条件。这是一种贪心策略始终维护每个长度下最优末尾最小的候选序列。4.3 完整代码实现与过程模拟import bisect # Python标准库提供二分查找 def length_of_lis_nlogn(nums): 计算最长上升子序列的长度 (O(n log n) 贪心二分查找解法) :param nums: List[int] 整数序列 :return: int 最长上升子序列的长度 if not nums: return 0 tails [] # tails[i] 表示长度为 i1 的LIS的最小末尾值 for x in nums: # 在 tails 中寻找第一个 x 的元素的位置 pos bisect.bisect_left(tails, x) # 如果 pos 等于 tails 的长度说明 x 比所有末尾都大 if pos len(tails): tails.append(x) # 延长 LIS else: tails[pos] x # 替换使该长度的LIS末尾更小 # tails 的长度就是 LIS 的长度 return len(tails) # 示例 nums [10, 9, 2, 5, 3, 7, 101, 18] print(length_of_lis_nlogn(nums)) # 输出4让我们手动模拟一下这个过程以nums [10, 9, 2, 5, 3, 7, 101, 18]为例x10:tails为空直接加入 -tails [10]x9: 在[10]中找第一个9的是10(pos0)替换 -tails [9](此时长度为1的LIS最小末尾从10优化为9)x2: 在[9]中找第一个2的是9(pos0)替换 -tails [2](继续优化末尾变为2)x5: 在[2]中找第一个5的找不到 (pos1等于长度)追加 -tails [2, 5](发现了更长的、长度为2的LIS如[2,5])x3: 在[2,5]中找第一个3的是5(pos1)替换 -tails [2, 3](优化长度为2的LIS末尾从5变为3[2,3]比[2,5]更优)x7: 在[2,3]中找第一个7的找不到 (pos2)追加 -tails [2, 3, 7](发现长度为3的LIS如[2,3,7])x101: 在[2,3,7]中找第一个101的找不到 (pos3)追加 -tails [2, 3, 7, 101](发现长度为4的LIS)x18: 在[2,3,7,101]中找第一个18的是101(pos3)替换 -tails [2, 3, 7, 18](优化长度为4的LIS末尾从101变为18。注意最终的tails数组[2,3,7,18]并不一定是原序列中真实存在的一个LIS但它保证了长度是正确的4并且每个位置都是该长度下的最小可能末尾。)复杂度分析时间复杂度O(n log n)。遍历n个元素每次在tails中进行二分查找O(log n)。空间复杂度O(n)tails数组最长可能为n。这个解法效率极高是处理大规模数据时的标准答案。但它有一个“缺点”tails数组最终存储的并不一定是真实的LIS它只能给出长度。如果需要输出具体的LIS序列则需要额外的记录复杂度会稍高一些。5. 两种解法的对比与选择策略现在我们已经掌握了两种解法该如何选择呢我画了一个对比表格方便你一目了然。特性维度O(n²) 动态规划解法O(n log n) 贪心二分查找解法核心思想计算以每个元素结尾的LIS长度状态转移。维护每个长度下LIS的最小末尾贪心优化。时间复杂度O(n²)O(n log n)空间复杂度O(n)O(n)能否输出具体序列可以。通过反向追踪dp数组比较容易重构出具体的LIS。直接不能。tails数组存储的不是真实序列。需要额外记录如记录前驱索引稍显复杂。代码复杂度低。逻辑直观双循环即可。中。需要理解贪心思想和二分查找的运用。适用场景1. 数据规模小 (n ≤ 5000)。2. 需要输出具体LIS序列。3. 初学者理解动态规划。1. 数据规模大 (n ≥ 10^4)。2. 只需求解长度。3. 追求极致效率。理解难度较低。是动态规划的经典入门案例。较高。需要理解“最小末尾”的贪心性质和二分查找的应用。选择建议应对笔试/竞赛优先掌握 O(n log n) 解法。因为出题人往往会把数据范围设得很大来卡 O(n²) 的算法。这是必须掌握的“标准答案”。面试场景如果面试官问起 LIS通常期望你两种都能讲出来。可以先从 O(n²) 的DP思路讲起分析其优缺点然后自然地引出优化思路最终给出 O(n log n) 的解法。这能很好地展示你的思维层次。工程项目根据实际数据量选择。如果序列长度可控且不大用DP代码更清晰易维护。如果处理的是流式数据或超长序列必须用优化解法。6. 常见变体问题与举一反三掌握了基础模型很多变体问题就可以迎刃而解。这里列举几个常见的6.1 最长非递减子序列允许相等这是 LIS 的一个直接变体。只需要在比较条件上把严格递增 () 改为非递减 () 即可。O(n²) DP解法将状态转移条件nums[j] nums[i]改为nums[j] nums[i]。O(n log n) 解法在二分查找时将bisect_left(找第一个大于等于x的位置) 改为bisect_right(找第一个大于x的位置)。因为允许相等我们希望用x替换掉第一个比它大的数而不是第一个大于等于它的数这样才能保证tails数组是非递减的。6.2 输出一个具体的最长上升子序列有时题目不仅要求长度还要求输出任意一个满足条件的序列。基于 O(n²) DP这是最方便的方法。我们在计算dp[i]时同时用一个prev[i]数组记录使得dp[i]取得最大值的前驱元素下标j。最后从dp值最大的位置i开始根据prev数组向前回溯即可得到序列。基于 O(n log n) 解法也可以实现但更复杂。需要在更新tails时不仅记录末尾值还要记录该末尾值在原序列中对应的索引并且要记录每个元素的前驱。实现起来代码量会大一些。6.3 二维 LIS 问题俄罗斯套娃信封问题这是一个著名的变体LeetCode 354。给你一堆信封的宽度和高度当另一个信封的宽度和高度都大于这个信封时它可以套进去。问最多能套多少层。解题思路这是一个二维的 LIS 问题。一个巧妙的解法是先将所有信封按宽度升序排序。这样在宽度维度上已经满足了“上升”的条件。对于宽度相同的信封按高度降序排序。为什么降序这是为了避免宽度相同的信封被错误地计入序列因为题目要求宽度和高度都严格大于。按高度降序后在寻找高度的 LIS 时宽度相同的信封由于其高度递减就不会形成递增序列从而保证了宽度的严格递增。排序后忽略宽度只对高度数组求最长严格上升子序列LIS。这个 LIS 的长度就是答案。这个问题的核心在于通过排序将二维问题降维到一维是 LIS 思想非常经典的应用。7. 实战中的踩坑点与调试技巧即便理解了算法自己实现时也难免出错。下面是我在多次实现和教学中总结的几个高频坑点。7.1 初始化与边界条件处理空序列这是最基本的边界条件。如果输入序列为空LIS 长度应该是 0。在函数开头一定要判断if not nums: return 0。dp数组初始化在 O(n²) DP 中dp[i]的初始值必须是 1。我曾见过有人初始化为 0导致结果永远比正确答案少 1。序列索引注意你的循环是从 0 开始还是从 1 开始。Python 中通常用range(n)和range(i)这很清晰。在其他语言中要小心数组越界。7.2 状态转移条件中的比较符号这是最隐蔽的错误之一。题目要求是“严格递增”还是“非递减”严格递增用。非递减用。 写代码前务必再读一遍题。我曾经在一次比赛中因为看错条件把写成导致一整道题白做。7.3 O(n log n) 解法中二分查找函数的选择在 Python 中bisect模块有bisect_left和bisect_right。bisect_left(a, x): 返回在有序数组a中插入x的最左位置使得插入后序列依然有序。如果x已存在则插入到已存在元素的左侧。它找到的是第一个大于等于 x的元素位置。bisect_right(a, x): 返回插入的最右位置。如果x已存在则插入到右侧。它找到的是第一个大于 x的元素位置。对于严格递增的 LIS我们应该使用bisect_left。因为我们希望用x替换掉第一个大于等于它的数这样可以保证tails数组严格递增。 对于非递减的 LIS我们应该使用bisect_right。用x替换第一个大于它的数以保证tails非递减。7.4 如何验证算法正确性构造测试用例不要只依赖题目给的样例。自己构造一些有代表性的测试用例极端情况空序列[]单元素序列[5]完全递减序列[5,4,3,2,1]答案应为1完全递增序列[1,2,3,4,5]答案应为5。包含重复元素[2,2,2]严格递增答案为1非递减答案为3。复杂序列[1,3,6,7,9,4,10,5,6]。可以手算一下再用两种算法跑一遍对比结果。随机大数据生成一个长序列用 O(n²) 和 O(n log n) 两种算法跑结果应该一致。这是验证优化算法正确性的好方法当然n 不能太大否则 O(n²) 跑不动。调试时可以在关键步骤打印中间变量。对于 DP 解法打印出每一步的dp数组。对于优化解法打印出每步更新后的tails数组。这能帮你直观地理解算法的执行过程。理解最长上升子序列不仅仅是解决一道题更是打开动态规划和贪心优化大门的一把钥匙。从最朴素的 O(n²) 状态定义到巧妙的 O(n log n) 贪心维护这个思考过程本身就极具价值。下次遇到序列相关的问题不妨先想想能不能排序能不能定义以某个位置结尾的状态能不能维护一个有序数组来优化多练习多思考这些经典的算法模型就会内化成你自己的解题直觉。