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开始计数）为结尾的、所有上升子序列中，最长的那个的长度。

这里有几个要点：

1. 以nums[i]结尾：这是一个限制条件。我们最终要求的答案是整个序列的 LIS 长度，它可能不以某个特定的i结尾。所以，我们的答案将是所有dp[i]中的最大值，即max(dp[0], dp[1], ..., dp[n-1])。
2. “最长的那个”：对于固定的结尾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]必须满足两个条件：

1. j < i（在i之前）。
2. 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

关键点与易错点分析：

1. dp数组初始化：dp = [1] * n这行代码很简洁地完成了初始化。确保你理解为什么是1。
2. 内层循环j的范围：for j in range(i)，这意味着j从 0 遍历到i-1。这是正确的，因为我们要找i之前的所有位置。
3. 状态转移的条件nums[j] < nums[i]：这里的<确保了严格递增。如果是非递减（允许相等），则应改为<=。
4. 状态转移操作dp[i] = max(dp[i], dp[j] + 1)：注意这里是max，因为我们可能从多个不同的j转移过来，要取能获得最大长度的那个。dp[i]的初始值是1，在内层循环中可能会被多次更新（变大）。
5. 最终返回值：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]的定义是：所有长度为i+1的上升子序列中，末尾元素的最小值。

• 为什么是i+1？因为数组下标通常从0开始，tails[0]就代表长度为1的LIS的最小末尾。
• 这个数组有一个重要性质：它一定是严格递增的。证明：假设tails[i]和tails[j]且i < j。tails[j]是某个长度为j+1的LIS的末尾，这个序列的前i+1个元素构成了一个长度为i+1的上升子序列，其末尾元素必然小于等于tails[j]（因为是子序列），而tails[i]是所有这种子序列末尾的最小值，所以有tails[i] < tails[j]（严格递增）。

4.2 算法流程与二分查找的运用

我们遍历原序列nums中的每个数x，然后去更新tails数组。更新规则如下：

1. 如果x比tails中所有元素都大，说明我们找到了一个更长的上升子序列，就将x添加到tails的末尾。此时tails的长度增加了1。
2. 否则，我们在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] 表示长度为 i+1 的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]为例：

1. x=10:tails为空，直接加入 ->tails = [10]
2. x=9: 在[10]中找第一个>=9的是10(pos=0)，替换 ->tails = [9]
   • (此时长度为1的LIS，最小末尾从10优化为9)
3. x=2: 在[9]中找第一个>=2的是9(pos=0)，替换 ->tails = [2]
   • (继续优化，末尾变为2)
4. x=5: 在[2]中找第一个>=5的找不到 (pos=1，等于长度)，追加 ->tails = [2, 5]
   • (发现了更长的、长度为2的LIS，如[2,5])
5. x=3: 在[2,5]中找第一个>=3的是5(pos=1)，替换 ->tails = [2, 3]
   • (优化长度为2的LIS，末尾从5变为3，[2,3]比[2,5]更优)
6. x=7: 在[2,3]中找第一个>=7的找不到 (pos=2)，追加 ->tails = [2, 3, 7]
   • (发现长度为3的LIS，如[2,3,7])
7. x=101: 在[2,3,7]中找第一个>=101的找不到 (pos=3)，追加 ->tails = [2, 3, 7, 101]
   • (发现长度为4的LIS)
8. x=18: 在[2,3,7,101]中找第一个>=18的是101(pos=3)，替换 ->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 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 问题。一个巧妙的解法是：

1. 先将所有信封按宽度升序排序。这样，在宽度维度上已经满足了“上升”的条件。
2. 对于宽度相同的信封，按高度降序排序。为什么降序？这是为了避免宽度相同的信封被错误地计入序列（因为题目要求宽度和高度都严格大于）。按高度降序后，在寻找高度的 LIS 时，宽度相同的信封由于其高度递减，就不会形成递增序列，从而保证了宽度的严格递增。
3. 排序后，忽略宽度，只对高度数组求最长严格上升子序列（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 如何验证算法正确性？构造测试用例

不要只依赖题目给的样例。自己构造一些有代表性的测试用例：

1. 极端情况：空序列[]，单元素序列[5]，完全递减序列[5,4,3,2,1]（答案应为1），完全递增序列[1,2,3,4,5]（答案应为5）。
2. 包含重复元素：[2,2,2]（严格递增答案为1，非递减答案为3）。
3. 复杂序列：[1,3,6,7,9,4,10,5,6]。可以手算一下，再用两种算法跑一遍，对比结果。
4. 随机大数据：生成一个长序列，用 O(n²) 和 O(n log n) 两种算法跑，结果应该一致。这是验证优化算法正确性的好方法（当然，n 不能太大，否则 O(n²) 跑不动）。

调试时，可以在关键步骤打印中间变量。对于 DP 解法，打印出每一步的dp数组。对于优化解法，打印出每步更新后的tails数组。这能帮你直观地理解算法的执行过程。

理解最长上升子序列，不仅仅是解决一道题，更是打开动态规划和贪心优化大门的一把钥匙。从最朴素的 O(n²) 状态定义，到巧妙的 O(n log n) 贪心维护，这个思考过程本身就极具价值。下次遇到序列相关的问题，不妨先想想，能不能排序？能不能定义以某个位置结尾的状态？能不能维护一个有序数组来优化？多练习，多思考，这些经典的算法模型就会内化成你自己的解题直觉。