子序列 DP：最长递增子序列与 $O (n lo g n)$ 优化

摘要

最长递增子序列（Longest Increasing Subsequence，LIS）是面试中最经典的子序列 DP 问题，也是考察”状态定义技巧”的典型案例。本文从 $O (n^{2})$ 的标准 DP 推导出发，详细阐述如何通过 patience sorting（耐心排序）的几何直觉，将 LIS 优化到 $O (n lo g n)$ ——一个在面试中极具区分度的知识点。最后通过 Russian Doll Envelopes（俄罗斯套娃信封）将 LIS 推广到二维场景，完整展示子序列 DP 的解题框架。

第 1 章子序列 vs 子串：概念辨析

1.1 子序列和子串的区别

在进入正题之前，必须澄清两个经常混淆的概念：

子串（Substring）：连续的一段字符/元素。"ace" 不是 "abcde" 的子串，但 "bcd" 是。

子序列（Subsequence）：不要求连续，只要求保持相对顺序。"ace" 是 "abcde" 的子序列（选位置 0、2、4），"aec" 不是（顺序错了）。

LIS 求的是子序列，不是子串。正是因为”不要求连续”这个特性，枚举所有子序列是 $O (2^{n})$ 的，需要 DP 来优化。

1.2 什么是最长递增子序列

给定序列 $A = [a_{1}, a_{2}, \dots, a_{n}]$ ，找出最长的严格递增子序列（strict increasing，即 $a_{i_{1}} < a_{i_{2}} < \dots < a_{i_{k}}$ ）的长度。

例：A = [10, 9, 2, 5, 3, 7, 101, 18]

LIS 之一：[2, 3, 7, 18]，长度 4。 LIS 之一：[2, 5, 7, 101]，长度 4。 LIS 之一：[2, 3, 7, 101]，长度 4。最长 LIS 长度 = 4。

第 2 章 $O (n^{2})$ DP 推导

2.1 「以某元素结尾」的状态定义技巧

LIS 的状态定义有两种候选：

候选 A：dp[i] = 数组前 i 个元素中，LIS 的长度。

问题：这个定义无法写出简洁的转移方程。dp[i] 到底是包含 A[i] 还是不包含 A[i]？如果不包含，转移自然；如果包含，则需要知道”以 A[i] 结尾的最长递增子序列”。不区分这两种情况，转移方程无法确定。

候选 B：dp[i] = 以 A[i] 结尾的最长递增子序列长度。

这个定义强制规定了”第 i 个元素一定被选，且是子序列的最后一个元素”。在这个定义下，转移方程自然：

$d p [i] = max_{j < i, A [j] < A [i]} (d p [j] + 1)$

含义：在所有”在 i 之前且值严格小于 A[i]”的位置 j 中，找以 A[j] 结尾的 LIS 最长的那个，加上 A[i] 本身（+1）。

核心概念：「以某元素结尾」的状态定义

在子序列 DP 中，“以第 i 个元素结尾”是一种非常强大的状态定义模式。它将”无限可能的子序列”固定到”必须包含 A[i] 且 A[i] 在末尾”这个更小的集合，使得转移方程可以明确写出。类似的定义在最长公共子序列、最大子数组和等问题中也大量使用。

2.2 初始化与遍历

初始化：dp[i] = 1 for all i（每个元素本身构成一个长度为 1 的递增子序列）
遍历顺序：正序，i 从 0 到 n-1；对每个 i，再遍历所有 j < i
最终答案：max(dp[0], dp[1], ..., dp[n-1])（注意不是 dp[n-1]，因为 LIS 未必以最后一个元素结尾）

2.3 完整实现

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);  // 每个元素单独构成长度 1 的 LIS
 
    int maxLen = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                // nums[j] 可以接在 nums[i] 前面（严格递增）
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

时间复杂度： $O (n^{2})$ （双重循环） 空间复杂度： $O (n)$ （dp 数组）

2.4 手工验证

nums = [10, 9, 2, 5, 3, 7, 101, 18]

i	nums[i]	j 满足 nums[j] < nums[i]	dp[i]
0	10	—	1
1	9	—	1
2	2	—	1
3	5	j=2 (2<5, dp[2]=1)	2
4	3	j=2 (2<3, dp[2]=1)	2
5	7	j=2(1→2), j=3(2→3), j=4(2→3)	3
6	101	j=0(1),j=1(1),j=2(1),j=3(2),j=4(2),j=5(3)	4
7	18	j=2(1),j=3(2),j=4(2),j=5(3)	4

最终 max(dp) = 4。✅

第 3 章 $O (n lo g n)$ 优化：Patience Sorting

3.1 为什么 $O (n^{2})$ 不够用

当 $n = 1 0^{5}$ 时， $O (n^{2}) = 1 0^{10}$ 次操作，远超 $1 0^{8}$ 的常规上限，必然超时。

LeetCode 300 在数据规模 $n = 2500$ 时， $O (n^{2})$ 勉强通过。但 Russian Doll Envelopes（ $n = 1 0^{5}$ ）就必须用 $O (n lo g n)$ 。

3.2 Patience Sorting：纸牌游戏的直觉

$O (n lo g n)$ 的 LIS 算法来自一个叫 patience sorting（耐心排序） 的纸牌游戏规则：

游戏规则：将一副牌从左到右逐一翻开，按以下规则将每张牌放到桌上的牌堆中：

如果当前牌的数字小于或等于某个牌堆顶部的牌，将它放到最左边满足条件的那堆的上面（替换掉顶部）
如果没有牌堆顶部 ≥ 当前牌，则新建一个牌堆

结论：游戏结束时，桌上的牌堆数量就是 LIS 的长度。

以 [10, 9, 2, 5, 3, 7, 101, 18] 为例，逐步模拟：

处理 10：没有牌堆，新建堆1 → 堆: [10]
处理  9：9 < 10（堆1顶部），放到堆1顶（替换）→ 堆: [9]
处理  2：2 < 9（堆1顶部），放到堆1顶（替换）→ 堆: [2]
处理  5：5 > 2（堆1顶部），新建堆2 → 堆: [2, 5]
处理  3：3 > 2（堆1顶），3 < 5（堆2顶），放到堆2顶（替换）→ 堆: [2, 3]
处理  7：7 > 2, 7 > 3，新建堆3 → 堆: [2, 3, 7]
处理 101：101 > 所有，新建堆4 → 堆: [2, 3, 7, 101]
处理 18：18 > 2, > 3, > 7, < 101，放到堆4顶（替换）→ 堆: [2, 3, 7, 18]

最终 4 个牌堆，LIS 长度 = 4。✅

3.3 算法的精妙：tails 数组

上面的模拟可以用一个 tails 数组来实现：

tails[i] 存储所有长度为 i+1 的递增子序列中，末尾元素的最小值（这是”替换”操作的本质）
维护 tails 数组的长度就是当前 LIS 的最大长度

关键性质：tails 数组始终是严格递增的。

证明：反设 tails[i] >= tails[i+1]，即长度 i+2 的递增子序列末尾元素 ≤ 长度 i+1 的递增子序列末尾元素。但长度 i+2 的子序列必然包含一个倒数第二个元素比末尾小，它可以接上长度 i 的子序列——矛盾。

tails 数组递增，因此可以用二分查找找到每个新元素应该放置的位置：

找到 tails 中第一个 ≥ nums[i] 的位置（即 lower_bound）
用 nums[i] 替换该位置（或追加到末尾，如果所有 tails 元素都 < nums[i]）

public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];  // tails[i] = 长度为 i+1 的 LIS 的最小末尾值
    int len = 0;  // 当前 LIS 的最大长度
 
    for (int num : nums) {
        // 在 tails[0..len-1] 中，用二分查找找到第一个 >= num 的位置
        int lo = 0, hi = len;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (tails[mid] < num) lo = mid + 1;
            else hi = mid;
        }
        // lo 是 num 应该插入/替换的位置
        tails[lo] = num;
        if (lo == len) len++;  // num 大于所有 tails，LIS 长度 +1
    }
    return len;
}

时间复杂度： $O (n lo g n)$ （每个元素一次二分查找， $O (lo g n)$ ） 空间复杂度： $O (n)$ （tails 数组）

生产避坑：tails 数组不代表真实的 LIS

tails 数组的元素可能不构成一个合法的递增子序列。它只是”各个长度的 LIS 的最优末尾值”。例如：nums = [3, 1, 4, 1, 5]，最终 tails = [1, 4, 5]（长度 3），但 [1, 4, 5] 确实是一个 LIS，只是某些情况下 tails 中的元素来自不同的实际子序列。如果题目要求输出具体的 LIS（不只是长度），需要用回溯 + 父节点追踪，不能直接输出 tails。

3.4 $O (n^{2})$ 与 $O (n lo g n)$ 的区别

方法	时间复杂度	能否输出具体 LIS	代码复杂度
$O (n^{2})$ DP	$O (n^{2})$	✅ 能（回溯父节点）	简单
$O (n lo g n)$ patience	$O (n lo g n)$	需要额外处理	稍复杂

面试中：

如果题目只要求 LIS 长度，O(n log n) 是加分项
如果要求输出具体 LIS，通常 O(n^2) DP 更易实现

第 4 章输出具体的 LIS

4.1 如何通过 dp 数组回溯

$O (n^{2})$ DP 维护了 dp[i]（以 nums[i] 结尾的 LIS 长度）。要还原具体的 LIS，需要额外记录每个位置的前驱：

public int[] findLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    int[] prev = new int[n];  // prev[i] = 在 LIS 中，i 的前一个元素的下标
    Arrays.fill(dp, 1);
    Arrays.fill(prev, -1);  // -1 表示没有前驱
 
    int maxLen = 1, maxIdx = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;  // 记录前驱
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            maxIdx = i;  // 记录 LIS 末尾位置
        }
    }
 
    // 从末尾反向追踪 LIS
    int[] lis = new int[maxLen];
    int idx = maxLen - 1;
    int curr = maxIdx;
    while (curr != -1) {
        lis[idx--] = nums[curr];
        curr = prev[curr];
    }
    return lis;
}

第 5 章 LeetCode 354：俄罗斯套娃信封

5.1 题目

LeetCode 354 - Russian Doll Envelopes（困难）

给你一个二维整数数组 envelopes，其中 envelopes[i] = [wi, hi] 表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大时，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组”俄罗斯套娃”信封。

注意：不允许旋转信封。

输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的序列为 [2,3] => [5,4] => [6,7]。

5.2 问题分析：二维 LIS

这道题本质上是二维 LIS：找一个信封序列，使得宽度和高度都严格递增。

朴素思路：先按宽度排序，然后对高度数组求 LIS。

但有一个陷阱：宽度相同的信封不能互相嵌套（需要严格大于）。如果直接按宽度正序排序，然后对高度做 LIS，那么对于宽度相同的多个信封，高度序列中递增的子序列可能包含多个宽度相同的信封——这是不合法的。

解决方案：

按宽度升序排列
宽度相同时，按高度降序排列

这样，宽度相同的信封在高度序列中是降序的。由于 LIS 要求严格递增，降序序列中只能选一个——自然地排除了”选多个同宽度信封”的非法情况。

排序后：[[2,3], [5,4], [6,7], [6,4]]

注意 [6,7] 和 [6,4]：宽度相同，高度按降序排 [7, 4]。
在高度序列 [3, 4, 7, 4] 中做 LIS，同宽度的 [7, 4] 中只能选一个（因为 7 > 4，不是递增）。

对排序后的高度序列 [3, 4, 7, 4] 做 LIS：

tails = [3]
tails = [3, 4]
tails = [3, 4, 7]
4 替换 7：tails = [3, 4, 4]…等等，4 替换 7，tails = [3, 4, 4]

这里有一个细节：LIS 要求严格递增，所以要找 tails 中第一个 ≥ num 的位置进行替换（不是 >）。

对 [3, 4, 7, 4]：

3 → tails = [3]，len=1
4 > 3 → tails = [3, 4]，len=2
7 > 4 → tails = [3, 4, 7]，len=3
4：找第一个 ≥ 4 的位置，是 tails[1] = 4，替换 → tails = [3, 4, 7]（4 替换 4，不变），len=3

答案 3。✅

5.3 完整实现

public int maxEnvelopes(int[][] envelopes) {
    // 按宽度升序，宽度相同时按高度降序排列
    Arrays.sort(envelopes, (a, b) -> {
        if (a[0] != b[0]) return a[0] - b[0];  // 宽度升序
        return b[1] - a[1];                     // 宽度相同，高度降序
    });
 
    // 对高度数组做 LIS（O(n log n) 版本）
    int[] tails = new int[envelopes.length];
    int len = 0;
 
    for (int[] env : envelopes) {
        int h = env[1];
        // 严格递增 LIS：找第一个 >= h 的位置
        int lo = 0, hi = len;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (tails[mid] < h) lo = mid + 1;
            else hi = mid;
        }
        tails[lo] = h;
        if (lo == len) len++;
    }
    return len;
}

时间复杂度： $O (n lo g n)$ （排序 $O (n lo g n)$ + LIS $O (n lo g n)$ ） 空间复杂度： $O (n)$

5.4 排序策略的正确性证明

为什么宽度相同时高度降序就能解决非法选取问题？

设有两个宽度相同的信封 $E_{1} = (w, h_{1})$ 和 $E_{2} = (w, h_{2})$ ， $h_{1} > h_{2}$ （降序排列后 $E_{1}$ 在 $E_{2}$ 前面）。

在 LIS 中，若同时选 $E_{1}$ 和 $E_{2}$ ，则需要 $h_{1} < h_{2}$ （严格递增）或 $h_{2} < h_{1}$ （反向）。由于我们按降序排， $h_{1} > h_{2}$ ，LIS 中不可能同时选二者（LIS 要求严格递增，而 $h_{1} > h_{2}$ ，不满足前者在后者前面的递增要求）。✅

第 6 章 LIS 相关的变体问题

6.1 最长不递减子序列（非严格 LIS）

有些题目要求”非递减”而非”严格递增”（即允许相等）。区别在于二分查找时：

严格递增：找第一个 >= num 的位置（lower_bound）
非递减：找第一个 > num 的位置（upper_bound）

// 非严格 LIS：允许相等，upper_bound
int lo = 0, hi = len;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (tails[mid] <= num) lo = mid + 1;  // <= 而非 <
    else hi = mid;
}
tails[lo] = num;

6.2 最长摆动子序列（LeetCode 376）

要求子序列的相邻元素交替升降。

不需要 DP，贪心即可（每次遇到摆动点就计入）。但理解 LIS 的思路有助于建立对”子序列结构”的感知。

6.3 最大子数组和（LeetCode 53）：另一种「结尾」DP

虽然不是子序列问题，但最大子数组和（Kadane 算法）使用了类似的”以某元素结尾”状态定义：

dp[i] = 以 nums[i] 结尾的子数组的最大和：

$d p [i] = max (n u m s [i], d p [i - 1] + n u m s [i])$

含义：以 nums[i] 结尾的最大子数组，要么只包含 nums[i] 本身（前面的子数组拖累了，不如重新开始），要么是以 nums[i-1] 结尾的最大子数组加上 nums[i]。

这和 LIS 的状态定义异曲同工。

第 7 章 LIS 的深度思考

7.1 Patience Sorting 的几何解释

把 nums 的每个元素想象成一张牌，patience sorting 的过程可以用几何来描述：

桌面上每堆牌的顶部构成了一个序列，这个序列始终严格递增（因为我们总是把牌放到”第一个顶部 ≥ 当前牌”的堆上，或者新建堆，维护了递增性）。

牌堆数 = LIS 长度的证明：

任何一个递增子序列中，相邻两个元素来自不同的牌堆（因为后一个元素比前一个元素大，而同一堆中后加入的牌比旧顶部小）
因此，一个长度为 $k$ 的递增子序列至少需要 $k$ 个牌堆
另一方面，我们可以从每个牌堆顶部各取一张牌构成递增序列（因为顶部序列是递增的），因此 LIS 长度等于牌堆数

7.2 Dilworth 定理：最长反链等于最小链覆盖

LIS 背后有一个更深的数学定理——Dilworth 定理：

在偏序集中，最长反链的大小等于最小链覆盖数（把所有元素分成若干个链所需的最少链数）。

对 LIS 问题，“链”是递增子序列，“反链”是不构成任何递增对的元素集合（即最长递减子序列）。Dilworth 定理告诉我们：

最长递增子序列的长度 = 将数组分成最少的递减子序列所需的数量

这不仅是一个数学美感的结论，也提供了一个完全不同的求 LIS 的角度：把数组分成最少的严格递减堆（即 patience sorting 的过程）。

第 8 章总结与高频题清单

8.1 LIS 求解方法总结

方法	时间复杂度	适用场景
$O (n^{2})$ DP	$O (n^{2})$	$n \leq 2500$ ，需要输出具体 LIS 时
$O (n lo g n)$ patience	$O (n lo g n)$	$n \leq 1 0^{5}$ ，只需 LIS 长度时

8.2 LIS 类题目汇总

题目	类型	关键技巧
LeetCode 300 Longest Increasing Subsequence	标准 LIS	$O (n^{2})$ 或 $O (n lo g n)$
LeetCode 354 Russian Doll Envelopes	二维 LIS	排序去掉一维，再做 LIS
LeetCode 673 Number of LIS	LIS 计数	额外维护 `cnt[i]` = 以 i 结尾的 LIS 数量
LeetCode 1143 Longest Common Subsequence	另一类子序列 DP	见下一篇

下一篇最长公共子序列与字符串编辑距离将介绍另一大类子序列 DP——两个序列之间的最优匹配，包括 LCS 和 Edit Distance。

汀的知识碎片

文章导航

04 子序列DP：最长递增子序列与O(nlogn)优化

子序列 DP：最长递增子序列与 $O (n lo g n)$ 优化

摘要

第 1 章子序列 vs 子串：概念辨析

1.1 子序列和子串的区别

1.2 什么是最长递增子序列

第 2 章 $O (n^{2})$ DP 推导

2.1 「以某元素结尾」的状态定义技巧

2.2 初始化与遍历

2.3 完整实现

2.4 手工验证

第 3 章 $O (n lo g n)$ 优化：Patience Sorting

3.1 为什么 $O (n^{2})$ 不够用

3.2 Patience Sorting：纸牌游戏的直觉

3.3 算法的精妙：tails 数组

3.4 $O (n^{2})$ 与 $O (n lo g n)$ 的区别

第 4 章输出具体的 LIS

4.1 如何通过 dp 数组回溯

第 5 章 LeetCode 354：俄罗斯套娃信封

5.1 题目

5.2 问题分析：二维 LIS

5.3 完整实现

5.4 排序策略的正确性证明

第 6 章 LIS 相关的变体问题

6.1 最长不递减子序列（非严格 LIS）

6.2 最长摆动子序列（LeetCode 376）

6.3 最大子数组和（LeetCode 53）：另一种「结尾」DP

第 7 章 LIS 的深度思考

7.1 Patience Sorting 的几何解释

7.2 Dilworth 定理：最长反链等于最小链覆盖

第 8 章总结与高频题清单

8.1 LIS 求解方法总结

8.2 LIS 类题目汇总

On this page

汀的知识碎片

文章导航

04 子序列DP：最长递增子序列与O(nlogn)优化

子序列 DP：最长递增子序列与 O(nlogn) 优化

摘要

第 1 章 子序列 vs 子串：概念辨析

1.1 子序列和子串的区别

1.2 什么是最长递增子序列

第 2 章 O(n2) DP 推导

2.1 「以某元素结尾」的状态定义技巧

2.2 初始化与遍历

2.3 完整实现

2.4 手工验证

第 3 章 O(nlogn) 优化：Patience Sorting

3.1 为什么 O(n2) 不够用

3.2 Patience Sorting：纸牌游戏的直觉

3.3 算法的精妙：tails 数组

3.4 O(n2) 与 O(nlogn) 的区别

第 4 章 输出具体的 LIS

4.1 如何通过 dp 数组回溯

第 5 章 LeetCode 354：俄罗斯套娃信封

5.1 题目

5.2 问题分析：二维 LIS

5.3 完整实现

5.4 排序策略的正确性证明

第 6 章 LIS 相关的变体问题

6.1 最长不递减子序列（非严格 LIS）

6.2 最长摆动子序列（LeetCode 376）

6.3 最大子数组和（LeetCode 53）：另一种「结尾」DP

第 7 章 LIS 的深度思考

7.1 Patience Sorting 的几何解释

7.2 Dilworth 定理：最长反链等于最小链覆盖

第 8 章 总结与高频题清单

8.1 LIS 求解方法总结

8.2 LIS 类题目汇总

On this page

子序列 DP：最长递增子序列与 $O (n lo g n)$ 优化

第 1 章子序列 vs 子串：概念辨析

第 2 章 $O (n^{2})$ DP 推导

第 3 章 $O (n lo g n)$ 优化：Patience Sorting

3.1 为什么 $O (n^{2})$ 不够用

3.4 $O (n^{2})$ 与 $O (n lo g n)$ 的区别

第 4 章输出具体的 LIS

第 8 章总结与高频题清单