动态规划经典——最长上升/不下降子序列问题（O(n2) 与 O(n log n) 详解）

子序列问题是算法竞赛中的常客，其中 最长上升子序列（LIS） 以及它的各种变体（不下降、下降、不上升）更是基础中的基础。本文将从零开始，用最直白的语言详细讲解 $O(n^2)$ 的朴素动态规划和 $O(n \log n)$ 的贪心+二分优化，并手把手带你写出一份自己也能看懂的代码。

阅读完本文，你将能够：

• 彻底理解两种写法的状态定义和转移过程
• 清晰区分“严格上升”与“不下降”写法上的细微差别
• 学会输出最长子序列的具体方案
• 轻松应对各种变体（最长下降、最长不上升、合唱队形等）

一、问题引入

给定一个长度为 $N$ 的整数序列 $a_1, a_2, \dots, a_N$，求最长的子序列（不一定连续），使得序列中的元素满足某种单调性，例如：

1. 严格递增：$a_{i_1} < a_{i_2} < \dots < a_{i_k}$
2. 不下降（非严格递增）：$a_{i_1} \le a_{i_2} \le \dots \le a_{i_k}$
3. 严格递减：$a_{i_1} > a_{i_2} > \dots > a_{i_k}$
4. 不上升（非严格递减）：$a_{i_1} \ge a_{i_2} \ge \dots \ge a_{i_k}$

下文中我们将以最经典的两种——最长严格上升子序列和最长不下降子序列为主线进行讲解，并扩展到其他类型。

二、$O(n^2)$ 朴素动态规划

可能要有一定动态规划基础

基础动态规划

动态规划1

动态规划2

2.1 状态定义

设 $dp[i]$ 表示 以第 $i$ 个元素结尾 的最长上升（或不下降）子序列的长度。

为什么这样定义？
因为子序列的最后一个元素决定了后续元素能否接上，所以将“结尾位置”作为状态是非常自然的。

2.2 转移方程

对于当前位置 $i$，我们向前扫描所有 $j < i$：

• 若求 严格上升，需满足 $a[j] < a[i]$：

  $$dp[i] = \max_{j < i,\ a[j] < a[i]} \{ dp[j] + 1 \}$$

• 若求 不下降，需满足 $a[j] \le a[i]$：

  $$dp[i] = \max_{j < i,\ a[j] \le a[i]} \{ dp[j] + 1 \}$$

如果找不到任何合法的 $j$，则 $dp[i] = 1$（自己单独成为一个长度为 1 的子序列）。

最终答案即为 $\max\{dp[i]\}$。

2.3 代码实现

以求 最长不下降子序列 为例：

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int a[N], dp[N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;                     // 初始化为1
        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 << endl;
    return 0;
}

若要求 严格上升，只需将13行条件改为 a[j] < a[i] 即可。

2.4 复杂度分析

两层循环使得时间复杂度为 $O(n^2)$，对于 $n \le 10^3$ 的数据完全足够，但当 $n$ 达到 $10^5$ 以上时就必须优化了。

三、O(n log n) 贪心思想 + 二分查找优化

不会二分查找的看这里1

不会二分查找的看这里2

3.1 核心思想

我们不再直接存储以每个元素结尾的长度，而是维护一个数组 $d$，其中 $d[k]$ 表示当前找到的长度为 $k$ 的子序列中，末尾元素的最小可能值。

为什么记录最小值？
因为末尾元素越小，后面的元素就越容易接上去，从而得到更长的子序列。这是一种典型的贪心思想。

$d$ 数组有一个非常重要的性质：它是单调递增（或非严格递增）的。这一点保证了我们可以使用二分查找来快速更新。

以严格上升子序列为例，$d$ 严格递增：
若 $len_1 < len_2$，则 $d[len_1] < d[len_2]$。
因为如果 $d[len_1] \ge d[len_2]$，我们可以用更短序列的末尾元素去替换更长的末尾，这与“最优”矛盾。

3.2 算法流程（以严格上升为例）

从头到尾遍历原序列的每个元素 $a[i]$：

1. 如果 $a[i] > d[len]$（当前最长长度 $len$ 的末尾），说明 $a[i]$ 可以接在长度为 $len$ 的子序列后面，形成一个长度为 $len+1$ 的新子序列，于是 d[++len] = a[i]。
2. 否则，在 $d[1 \dots len]$ 中找到第一个 大于等于 $a[i]$ 的位置 $pos$，并用 $a[i]$ 替换 $d[pos]$。这一步意味着：我们找到了一个长度与 $pos$ 相同、但末尾元素更小（或相等）的子序列，使该长度的末尾值变得更优。

遍历结束后，$len$ 即为答案。

3.3 两种变体：lower_bound 还是 upper_bound？

这是初学者最容易混淆的地方。我们用一张表来彻底理清：

为什么会有这样的区别？

• 严格上升时，子序列不允许相等，所以 $d$ 中不能出现相等的元素。用 lower_bound 找到第一个 $\ge a[i]$ 的位置，如果找到的刚好等于 $a[i]$，替换它不会产生相等的元素（因为原本就是相等的，替换后长度不变，末尾值也不变），实际上是保持严格性。
• 不下降时，允许相等，因此 $d$ 中可能出现相等元素。为了在相等时能够扩展长度，我们只替换 严格大于 $a[i]$ 的元素，保留相等的，所以用 upper_bound 查找第一个 $> a[i]$ 的位置。

3.4 代码实现

求最长不下降子序列长度：

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

const int N = 100005;
int a[N], d[N];

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

    int len = 1;
    d[1] = a[1];
    for (int i = 2; i <= n; i++) {
        if (a[i] >= d[len]) {                     // 不下降：允许相等
            d[++len] = a[i];
        } else {
            int pos = upper_bound(d + 1, d + len + 1, a[i]) - d;
            d[pos] = a[i];
        }
    }
    cout << len << endl;
    return 0;
}

求最长严格上升子序列长度：

// 只改两个地方：
if (a[i] > d[len]) {          // 严格大于
    d[++len] = a[i];
} else {
    int pos = lower_bound(d + 1, d + len + 1, a[i]) - d;
    d[pos] = a[i];
}

3.5 模拟演示

以序列 1 3 2 8 5 6，求最长不下降子序列为例：

• 初始：d[1] = 1，len = 1
• i=2, a[2]=3：3 >= 1，扩展 → d[2]=3，len=2
• i=3, a[3]=2：2 < 3，二分 upper_bound 找到第一个 >2 的位置是 d[2]=3，替换 → d[2]=2，d=[1,2]
• i=4, a[4]=8：8 >= 2，扩展 → d[3]=8，d=[1,2,8]
• i=5, a[5]=5：5 < 8，替换 d[3] → d[3]=5，d=[1,2,5]
• i=6, a[6]=6：6 >= 5，扩展 → d[4]=6，d=[1,2,5,6]，len=4

最终答案 4，与题意一致。

四、输出最长子序列的明细

很多题目不仅要求长度，还要输出具体的子序列。在 $O(n \log n)$ 算法中，由于 $d$ 数组只存储末尾元素，丢失了中间信息，我们需要额外维护 前驱指针。

4.1 思路

设 $fa[i]$ 表示以 $a[i]$ 结尾的子序列中，$a[i]$ 的前一个元素在原数组中的下标。
在更新 $d$ 数组的同时记录 $fa[i]$：

• 当 $a[i]$ 直接扩展长度时，它的前驱就是 $d[k]$ 所对应的元素下标。
• 当 $a[i]$ 替换 $d[pos]$ 时，它的前驱就是 $d[pos-1]$ 对应的元素下标。

为了能够通过 $d$ 数组找到对应元素的下标，我们让 $d$ 不再只存储值，而是存储一个结构体，包含值 x 和它在原数组中的位置 id。

最后，从 $d[len]$ 的 id 出发，沿着 $fa$ 数组回溯，即可得到子序列（逆序），用递归或栈正序输出。

4.2 参考代码

以最长不下降子序列为例：

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

const int N = 1000005;
int a[N], fa[N], n, len;

struct Node {
    int x;   // 元素的值
    int id;  // 在原序列中的下标
} d[N];

// 递归输出序列
void print(int i) {
    if (fa[i] == -1) {
        cout << a[i] << " ";
        return;
    }
    print(fa[i]);
    cout << a[i] << " ";
}

// upper_bound 的自定义比较函数
bool cmp(int val, Node node) {
    return val < node.x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    memset(fa, -1, sizeof(fa));
    len = 1;
    d[1].x = a[1];
    d[1].id = 1;

    for (int i = 2; i <= n; i++) {
        if (a[i] >= d[len].x) {
            d[++len].x = a[i];
            d[len].id = i;
            fa[i] = d[len - 1].id;
        } else {
            int pos = upper_bound(d + 1, d + len + 1, a[i], cmp) - d;
            d[pos].x = a[i];
            d[pos].id = i;
            fa[i] = d[pos - 1].id;
        }
    }

    cout << len << "\n";
    print(d[len].id);
    return 0;
}

如果要求的是严格上升，只需将条件改为 a[i] > d[len].x，并将 upper_bound 换成 lower_bound（注意自定义比较函数可能需要调整，也可以直接传 a[i] 并利用 Node 的 operator< 重载，但为了简洁可直接用 lower_bound(d+1, d+len+1, a[i], [](Node node, int val){ return node.x < val; }) 等方式）。

五、全类型变体及技巧总结

掌握了严格上升和不下降，其他变体只需做简单变换即可。

注意：lower_bound 和 upper_bound 默认要求数组升序。如果数组是降序排列（处理下降/不上升时），需要传入 greater<int>() 作为比较函数，且此时逻辑会反转：

• lower_bound(begin, end, val, greater<>()) 找到第一个 小于等于 val 的位置（因为数组是降序，“不小于”即“小于等于”）
  建议初学者统一使用“反转数组”或“反向遍历”的方法，不易出错。

六、经典练习题与题解

下面给出四道覆盖不同变体的经典题目，附详细题解和代码。

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

const int N = 100005;
int a[N], d[N];

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

    int len = 1;
    d[1] = a[1];
    for (int i = 2; i <= n; i++) {
        if (a[i] > d[len]) {
            d[++len] = a[i];
        } else {
            int pos = lower_bound(d + 1, d + len + 1, a[i]) - d;
            d[pos] = a[i];
        }
    }
    cout << len << endl;
    return 0;
}

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

const int N = 100005;
int a[N], f[N], g[N], d[N];

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

    // 正向 LIS
    int len = 1;
    d[1] = a[1];
    f[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (a[i] > d[len]) {
            d[++len] = a[i];
        } else {
            int pos = lower_bound(d + 1, d + len + 1, a[i]) - d;
            d[pos] = a[i];
        }
        f[i] = len; // 注意：这里存储的是以a[i]结尾的LIS长度，但严格来说O(n log n)维护的len是全局最长，无法直接得到以每个i结尾的精确长度。因此通常本题的正解是O(n^2) DP，或者在O(n log n)时额外记录每个i插入时的长度（可通过记录插入位置获取）。为便于演示，这里使用O(n^2) DP更加稳妥。但考虑到n可能较大，可用下面技巧：在二分插入时记录pos作为以i结尾的长度。
    }
    // 更精确的O(n log n)写f[i]：每次都记录插入/扩展时的长度
    // 重写一遍正向：
    len = 0;
    for (int i = 1; i <= n; i++) {
        int pos = lower_bound(d + 1, d + len + 1, a[i]) - d;
        d[pos] = a[i];
        if (pos > len) len = pos;
        f[i] = pos;   // 此时以a[i]结尾的最长上升长度就是pos
    }

    // 反向 LIS（从右向左做严格上升，即原序列的下降）
    memset(d, 0, sizeof(d));
    len = 0;
    for (int i = n; i >= 1; i--) {
        int pos = lower_bound(d + 1, d + len + 1, a[i]) - d;
        d[pos] = a[i];
        if (pos > len) len = pos;
        g[i] = pos;
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, f[i] + g[i] - 1);
    }
    cout << n - ans << endl;
    return 0;
}

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

const int N = 100005;
int a[N], d[N], n;

int main() {
    // 读入直到文件尾，或者给定个数，这里假设先输入n
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 第一问：最长不上升子序列
    // 方法：将数组反转求最长不下降，或直接用d维护降序
    int len = 0;
    for (int i = 1; i <= n; i++) {
        // 在降序数组中找第一个小于a[i]的位置（即允许相等时不替换相等的）
        // 由于是不上升，允许相等，d降序排列
        // 使用 upper_bound 配合 greater<int>()，找到第一个小于a[i]的位置
        int pos = upper_bound(d + 1, d + len + 1, a[i], greater<int>()) - d;
        d[pos] = a[i];
        if (pos > len) len = pos;
    }
    cout << len << endl;

    // 第二问：最少系统数 = 最长严格上升子序列长度
    memset(d, 0, sizeof(d));
    len = 0;
    for (int i = 1; i <= n; i++) {
        int pos = lower_bound(d + 1, d + len + 1, a[i]) - d;
        d[pos] = a[i];
        if (pos > len) len = pos;
    }
    cout << len << endl;

    return 0;
}

七、总结

• 子序列问题的核心是 DP，$O(n^2)$ 的思路最简单，适合小数据。
• $O(n \log n)$ 的写法通过维护各长度末尾最小值来贪心扩展，借助二分将转移优化到 $\log n$。
• 二分函数的选择是易错点：
  • 严格上升 → lower_bound
  • 不下降 → upper_bound
  • 严格下降 / 不上升 → 反转数组或使用 greater<>() 的二分。
• 若需输出具体方案，额外维护前驱数组，回溯即可。
• 常见的合唱队形、导弹拦截等问题，本质是多个方向子序列的组合应用。

希望这篇博客能帮助你彻底攻克最长上升/不下降子序列及其变体。如果有任何疑问，欢迎在评论区交流讨论！

附：全类型对比速查表

附：dxd上课笔记

熟练掌握这些，你就能应对绝大部分子序列相关的考题了。