最长递增子序列：从 DP 到贪心二分

1. 课程导引与核心价值分析

在动态规划（Dynamic Programming, DP）的学习路径中，“最长递增子序列（Longest Increasing Subsequence, 简称 LIS）”具有举足轻重的战略地位。它不仅是线性 DP 的经典范式，更是区分“基础理解”与“深度掌握”的分水岭。

LIS 的核心意义在于它完美诠释了**“枚举选哪个”**这一思维模型。与 0-1 背包这类“选或不选”的逻辑不同，LIS 要求我们在决策当前状态时，必须回溯并审视之前所有的局部最优解，从中寻找那个最合适的前驱。掌握 LIS，意味着你具备了处理非连续子序列优化问题的能力，能够熟练地在 O(n²) 的直觉解法与 O(n log n) 的极致优化之间进行思维切换。

本报告的目标是引导你像资深架构师一样思考：不仅能写出代码，更能从状态定义的本质出发，推导至基于“Lower Bound”的高效算法，并在面试中复现这一演进过程。

2. 题目原型：LeetCode 300. 最长递增子序列

题目核心： 给定一个整数数组 nums，返回其中最长严格递增子序列的长度。

  • 输入： nums = [10, 9, 2, 5, 3, 7, 101, 18]
  • 输出： 4

典型示例推导： 数组 [10, 9, 2, 5, 3, 7, 101, 18] 中，存在多个长度为 4 的子序列：

  • [2, 3, 7, 101]
  • [2, 5, 7, 18]

这些序列均满足“相对位置不变”且“严格递增”，因此结果为 4。

面试官关注的关键词：

  1. 严格递增： 意味着相邻元素必须满足 a_i < a_{i+1}（若题目要求“不降”，则为 a_i ≤ a_{i+1}）。
  2. 子序列： 这是一个关键点，子序列不要求连续，只需保持原数组中的相对顺序。

3. 算法核心思路一：动态规划 (Dynamic Programming)

动态规划是此类问题的直觉起点。要理解 LIS 的 DP，首先要厘清状态定义的深层逻辑。

深度解析状态定义

这是面试中最易混淆的地方。根据灵茶山艾府专家的建议，我们需要区分两种模型：

  • “选或不选”模型： 如 0-1 背包或最长公共子序列（LCS），通常定义状态为“前 i 个元素”的最优值。
  • “枚举选哪个”模型： 如本题 LIS。我们必须定义 f[i] 为**“以第 i 个元素结尾的最长递增子序列的长度”**。

为什么必须“以第 i 个元素结尾”？ 因为子序列是否可以继续延伸，完全取决于它最后一个元素的大小。只有固定了末尾元素，我们才能在处理后续元素时，通过大小比较来判断是否能进行转移。

推导转移方程

为了计算 f[i]，我们需要观察所有在 i 之前的元素 j (0 ≤ j < i)：

  • 若 nums[j] < nums[i]，则 nums[i] 可以接在以 nums[j] 结尾的序列后面。
  • 转移方程： f[i] = max(f[j]) + 1，其中 0 ≤ j < i 且 nums[j] < nums[i]
  • 最终结果： max(f)

复杂度分析

  • 时间复杂度： O(n²)。需要双重循环枚举。
  • 空间复杂度： O(n)。需要一个数组存储每个位置的 DP 值。
  • 局限： 当 n > 10⁴ 时，O(n²) 将面临超时风险，必须引入贪心与二分的优化。

为了将效率提升至 O(n log n)，我们需要改变视角：如何让子序列增长得尽可能慢？

核心贪心策略

如果我们要让序列尽量长，那么序列末尾的数字应该越小越好。这样，它对后续元素的“包容度”就更高。

模拟执行过程与“Lower Bound”

维护一个辅助数组 g，其中 g[i] 表示长度为 i+1 的递增子序列末尾元素的最小值。

  1. 遍历 nums 中的每个元素 x。
  2. 若 x > g.back()，直接将其追加到 g 末尾。
  3. 否则，在 g 中通过二分查找找到第一个大于等于 x 的元素（即 Lower Bound），并用 x 替换它。

正确性证明：长度与内容的解耦

注意： 数组 g 最终的元素序列可能并不是一个合法的子序列。

  • 反例证明： nums = [3, 5, 1]
    • 处理 3：g = [3]
    • 处理 5：g = [3, 5]
    • 处理 1：二分查找第一个 ≥ 1 的位置，替换 3。g = [1, 5]
  • 结论： [1, 5] 并不是原数组的子序列，但其长度 2 正确反映了 LIS 的长度。这种替换操作虽然破坏了“内容”，但通过贪心保证了“长度”的正确演进。

性能评估

维度 动态规划 (DP) 贪心 + 二分查找
时间复杂度 O(n²) O(n log n)
处理规模 10⁴ 级别 10⁵ 及以上
核心逻辑 暴力枚举前驱 维护增长最慢的末尾

5. 代码实现与关键细节分析

高质量 Python 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from bisect import bisect_left

def length_of_lis(nums: list[int]) -> int:
    if not nums:
        return 0
    
    # g[i] 记录长度为 i+1 的递增子序列末尾的最小值
    g = []
    
    for x in nums:
        # 使用标准库实现 Lower Bound (第一个 >= x 的位置)
        # 面试技巧：如果是严格递增，用 bisect_left (>=)；如果不降，用 bisect_right (>)
        idx = bisect_left(g, x)
        
        if idx == len(g):
            # x 比当前所有末尾都大，可以延长 LIS
            g.append(x)
        else:
            # 贪心替换：用更小的 x 替换掉旧的末尾，为后续留空间
            g[idx] = x
            
    return len(g)

资深教练的易错点清单

  1. “严格”与“非严格”的判定：
    • 严格递增： 查找第一个 ≥ x 的位置进行替换（代码中使用 bisect_left）。
    • 非严格递增： 查找第一个 > x 的位置进行替换（代码中使用 bisect_right）。
  2. 初始值设定： 在 O(n²) 的 DP 中，f[i] 必须初始化为 1，因为每个元素自成一个长度为 1 的子序列。
  3. [高级面试加分项] O(1) 空间优化： 在某些面试场景中，若允许修改原数组，我们可以直接利用 nums 的前部空间充当辅助数组 g。通过维护一个 size 指针指向“伪数组”的末尾，实现 O(1) 额外空间开销。

6. 总结、模板提炼与举一反三

LIS 是子序列问题的基石。理解它的关键在于：DP 解决的是“怎么选”，而贪心+二分解决的是“如何更高效地选”。

LIS 算法模板 (通用版)

1
2
3
4
5
6
7
8
9
10
11
def lis_template(nums, strictly=True):
    g = []
    for x in nums:
        # 严格递增找 >= x，非严格递增找 > x
        import bisect
        idx = bisect.bisect_left(g, x) if strictly else bisect.bisect_right(g, x)
        if idx == len(g):
            g.append(x)
        else:
            g[idx] = x
    return len(g)

举一反三：题型演化矩阵

通过将问题转化为 LIS，可以解决一系列高频面试题：

模式 典型题目 转化技巧
维度压缩 354. 俄罗斯套娃信封 按宽升序、高降序排列，对“高”求 LIS
双向组合 1671. 得到山形数组的最少删除次数 正向 LIS + 反向 LIS，寻找 f[i] + b[i] 的最大值
数组分段 2111. 使数组 K 递增的最少操作次数 将数组按模 K 分组，每组分别求 LIS
序列约束 1964. 找出有效障碍赛路线 / 1626. 无矛盾球队 根据题目约束（如年龄、分数）排序后转化为 LIS

结语： 真正的算法掌握不在于背诵，而在于手动模拟。建议在草稿纸上模拟一次 [3, 5, 1, 4, 2] 的 g 数组变化过程，你会瞬间理解贪心替换的精妙所在。

数据结构与算法
#Python #动态规划 #LeetCode #数据结构与算法 #算法面试 #贪心
最长递增子序列：从 DP 到贪心二分
http://baikelwang.github.io/2026/06/15/最长递增子序列：从 DP 到贪心二分/
作者
北海
发布于
2026年6月15日
许可协议