最长上升子序列

一句话算法

LIS 先问“每个数能接在谁后面”，再用二分维护“同样长度下结尾越小越好”。

问题模型

给定一个长度为 $n$ 的序列：

求一个最长的严格上升子序列长度。

子序列可以删除若干元素，但不能改变剩余元素的相对顺序。严格上升表示相邻选中元素满足：

例如序列：

10 9 2 5 3 7 101 18

一个最长上升子序列是：

2 3 7 18

长度为 4。

核心直觉

以谁结尾

如果一个上升子序列最后选了 a[i]，那么它前一个元素只能来自 i 之前，并且值必须小于 a[i]。

所以 a[i] 可以接在所有满足：

j < i 且 a[j] < a[i]

的位置后面。

这就是 $O(n^2)$ DP 的直觉。

结尾越小越有前途

如果有两个上升子序列长度都等于 len：

... 8
... 5

那么末尾是 5 的那个更有前途，因为它更容易接上后面的数字。

所以对每个长度 len，只需要记住“长度为 len 的上升子序列中，最小可能结尾是多少”。这个数组天然单调，可以用二分维护。

状态设计

$O(n^2)$ 动态规划

定义：

表示以 $a_i$ 作为最后一个元素的最长严格上升子序列长度。

边界：

因为只选 $a_i$ 本身，也能形成长度为 $1$ 的上升子序列。

$O(n \log n)$ 二分优化

定义数组 tail：

tail[len - 1] = 长度为 len 的严格上升子序列中，末尾元素的最小可能值

例如 tail = [2, 3, 7] 表示：

• 长度为 1 的上升子序列，最小结尾是 2；
• 长度为 2 的上升子序列，最小结尾是 3；
• 长度为 3 的上升子序列，最小结尾是 7。

状态转移

对于 $O(n^2)$ 做法，枚举所有 j < i：

条件是：

最终答案：

对于二分优化做法，依次处理每个数 x：

1. 在 tail 中找到第一个 >= x 的位置。
2. 如果找不到，说明 x 可以接在当前最长序列后面，追加到 tail。
3. 如果找到了，用 x 替换这个位置，让对应长度的结尾尽量小。

tail 的长度就是 LIS 长度。

算法步骤

$O(n^2)$ 做法

1. 读入序列。
2. 初始化所有 dp[i] = 1。
3. 从左到右枚举 i。
4. 枚举所有 j < i。
5. 如果 a[j] < a[i]，用 dp[j] + 1 更新 dp[i]。
6. 所有 dp[i] 的最大值就是答案。

$O(n \log n)$ 做法

1. 维护一个空数组 tail。
2. 从左到右处理每个数 x。
3. 在 tail 中二分第一个 >= x 的位置。
4. 找不到就追加，找到了就替换。
5. 最后 tail.size() 就是答案。

算法证明

$O(n^2)$ DP 正确性

核心不变量：处理完位置 $i$ 后，dp[i] 等于所有以 $a_i$ 结尾的上升子序列中的最大长度。

1. 边界正确

   只选择 $a_i$ 一个数时，一定是合法上升子序列，所以 dp[i] 至少为 $1$。

2. 转移完整

   任意一个以 $a_i$ 结尾、长度大于 $1$ 的上升子序列，它的倒数第二个元素一定是某个 $a_j$，并满足：

   $$j < i,\quad a_j < a_i$$

3. 转移最优

   如果倒数第二个元素是 $a_j$，前半段的最优长度就是 dp[j]，接上 $a_i$ 后长度为：

   $$dp[j]+1$$

   对所有合法 $j$ 取最大值，就覆盖了所有可能的前驱。

因此 $O(n^2)$ 转移正确。

二分优化正确性

核心不变量：处理到当前位置后，tail[len - 1] 是长度为 len 的上升子序列的最小可能结尾。

1. 为什么可以替换

   如果一个长度为 len 的上升子序列结尾更小，它不会让已有长度变短，反而更容易接上后面的数。

2. 为什么用 lower_bound

   对严格上升子序列，x 应该替换第一个 >= x 的结尾。这样可以保持：

   • 小于 x 的长度可以被 x 接上；
   • 大于等于 x 的结尾被改小或保持不变。

3. 为什么 tail 长度是答案

   每次追加时，确实构造出了更长的上升子序列；每次替换时，只改善某个长度的最小结尾，不虚增长度。

所以处理完所有元素后，tail.size() 就是 LIS 长度。

复杂度分析

设序列长度为 $n$。

• $O(n^2)$ DP：时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。
• 二分优化：时间复杂度 $O(n \log n)$，空间复杂度 $O(n)$。

竞赛中如果 $n \le 5000$，$O(n^2)$ 通常可以接受；如果 $n$ 达到 $10^5$，应优先使用二分优化。

代码实现

$O(n^2)$ DP：

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

        #include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // dp[i]: 以 a[i] 作为最后一个元素的最长严格上升子序列长度。
    vector<int> dp(n + 1, 1);

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }

    cout << ans << "\n";
    return 0;
}
    

$O(n \log n)$ 二分优化：

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

        #include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> tail;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        // tail[len - 1]: 长度为 len 的严格上升子序列中，末尾元素的最小可能值。
        auto it = lower_bound(tail.begin(), tail.end(), x);
        if (it == tail.end()) {
            tail.push_back(x);
        } else {
            *it = x;
        }
    }

    cout << tail.size() << "\n";
    return 0;
}
    

测试用例

输入：

8
10 9 2 5 3 7 101 18

输出：

4

解释：2 3 7 18 是一个最长上升子序列。

边界用例：

5
5 5 5 5 5

严格上升答案是：

1

如果题目要求非下降子序列，答案才是 5。

应用分类详解

LIS 的本质是：在保持原相对顺序的前提下，找一个满足单调条件的最长选择序列。只要题目中出现“按原顺序选择”“最长递增”“删除最少元素后有序”，就应该优先考虑 LIS。

一、最长单调子序列

典型模式： 给一个序列，直接求最长上升、下降、非下降或非上升子序列。

识别信号： 出现“子序列”“最长上升”“最长不下降”“导弹拦截”。

核心建模： 把每个位置作为结尾，或用 tail 维护不同长度的最优结尾。

二、最少删除使序列有序

典型模式： 删除尽量少的元素，使剩下的序列满足上升或非下降。

识别信号： 出现“最少删除”“保留最多”“使序列递增”。

核心建模： 保留下来的最多元素就是 LIS，最少删除数为：

三、二维偏序中的最长链

典型模式： 每个元素有两个属性，要求两个属性都递增，选最长链。

识别信号： 出现“宽高”“二维点”“信封嵌套”“两个条件同时变大”。

核心建模： 先按第一维排序，再在第二维上做 LIS。排序时要处理相同第一维，避免错误地把不能共存的元素接起来。

四、LCS 的排列优化

典型模式： 两个序列都是排列，要求最长公共子序列。

识别信号： 两个序列元素互不重复，直接 LCS 会超时。

核心建模： 把第一个排列中的每个值映射成位置，再把第二个排列转换成位置序列；此时公共子序列等价于位置序列中的 LIS。

经典例题

1. luogu-B3637

LIS 模板题。适合先写 $O(n^2)$，再换成 $O(n \log n)$ 二分优化。

2. luogu-P1020

导弹拦截。需要区分最长不上升子序列和最少拦截系统数，能训练对“严格/非严格”条件的判断。

3. luogu-P1091

合唱队形。对每个位置分别求左侧 LIS 和右侧 LIS，再枚举峰顶。

4. luogu-P1439

排列 LCS。直接二维 LCS 会超时，关键是把第二个排列变成第一个排列中的位置序列，然后求 LIS。

参考

• 本文旧版解析保留的核心思路：把问题转成“以第 $i$ 个元素为结尾”的子问题。
• CLRS: Dynamic Programming.