最长不下降子序列

题意

给定一个长度为 $n$ 的整数序列，求最长不下降子序列的长度，并输出任意一组方案。

子序列可以不连续，但下标必须递增，选出的数满足前一个不大于后一个。

以下面的序列为例：

3 1 2 2 5 4 0

最长长度为 $4$，一种方案为 1 2 2 4。

输入 $n$ 和 $n$ 个整数；第一行输出最长长度，第二行输出一组子序列。约定 $1\le n\le2\times10^5$，$|a[i]|\le10^9$。

一、$O(n^2)$：枚举前驱

1. 状态与转移

设 $dp[i]$ 表示以 $a[i]$ 结尾的最长不下降子序列长度。

枚举 $a[i]$ 前面的数：如果 $j<i$ 且 $a[j]\le a[i]$，就可以接在以 $a[j]$ 结尾的子序列后面。

$$dp[i]=\max\left(1,\ \max_{\substack{j<i\\a[j]\le a[i]}}\{dp[j]+1\}\right)$$

其中 $1$ 表示只选择 $a[i]$。按下标从小到大计算，答案为所有 $dp[i]$ 的最大值。

i	1	2	3	4	5	6	7
a[i]	3	1	2	2	5	4	0
dp[i]	1			3	4		1

例如，第 $4$ 个数 $2$ 可以接在第 $3$ 个数 $2$ 后面，所以 $dp[4]=dp[3]+1=3$。注意，不下降允许相等。

2. 参考代码

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

const int N = 200005;
int n, a[N], dp[N], len;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        dp[i] = 1;
        for (int j = 1; j < i; ++j) 
            if (a[j] <= a[i])   dp[i] = max(dp[i], dp[j] + 1);
        len = max(len, dp[i]);
    }
    cout << len << '\n';
    return 0;
}

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$，适合 $n$ 为几千的情况。

二、$O(n\log n)$：贪心与二分

1. 优化的提示：能否少枚举一些前驱？

第一种做法每次都要枚举前面的所有位置。考虑两个长度相同的子序列：

长度为 3，结尾为 5
长度为 3，结尾为 2

后面遇到 $4$ 时，只能接在结尾为 $2$ 的子序列后面；遇到 $6$ 时，两者都能接。

所以，长度相同时，结尾越小越有利。求长度时，每种长度只需保留最小结尾值。

我们换一种状态定义：

$$dp[k]=\text{已处理的元素中，长度为 }k\text{ 的不下降子序列的最小结尾值}$$

用 $len$ 记录目前的最长长度，只有 $dp[1]$ 到 $dp[len]$ 有效。

注意，两种做法中 dp 的含义不同：前一种按结束位置记录长度，这一种按子序列长度记录最小结尾值。

2. 为什么能用二分？

这个数组满足：

$$dp[1]\le dp[2]\le\cdots\le dp[len]$$

理由是：取一个长度为 $k+1$、结尾为 $dp[k+1]$ 的子序列，去掉最后一个数，就得到长度为 $k$ 的子序列，其结尾不大于 $dp[k+1]$。而 $dp[k]$ 是长度为 $k$ 的最小结尾，因此 $dp[k]\le dp[k+1]$。

处理当前数 $x=a[i]$ 时，要找到它能接上的最长长度，也就是最大的 $k$，使：

$$dp[k]\le x$$

由于 dp 不下降，满足条件的位置一定是一段前缀，因此可以二分找到第一个大于 $x$ 的位置 $p$，它前面的 $p-1$ 个位置都满足条件。

于是，以 $x$ 结尾的最长长度就是 $p$。

3. 如何更新？

分为两种情况：

• 若 $x\ge dp[len]$，可以接在当前最长子序列后面，令 $dp[++len]=x$。
• 否则，找到第一个 $dp[p]>x$ 的位置，令 $dp[p]=x$。长度没有增加，但长度为 $p$ 的最小结尾变小了。

第二种情况中，$dp[p-1]\le x<dp[p]$；当 $p=1$ 时，直接用 $x$ 开始一个长度为 $1$ 的子序列。

查找代码：

int p = upper_bound(dp + 1, dp + len + 1, a[i]) - dp;

必须使用 upper_bound，寻找第一个严格大于当前数的位置。 相等的数可以继续接上，例如 2 2 2 的答案应为 $3$；使用 lower_bound 会把它误算成严格上升子序列。

4. dp 与 c 数组的变化示例

为了输出方案，增加数组：

$$c[i]=\text{以 }a[i]\text{ 结尾的最长不下降子序列长度}$$

因此，每次将 $a[i]$ 放到 dp 的第 $p$ 个位置时，记录 $c[i]=p$。它对应的就是第一种做法中的 $dp[i]$。

对序列 3 1 2 2 5 4 0，处理过程如下：

i	a[i]	操作	更新后的有效 dp	c[i]
1	3	开始	3	1
2	1	替换第 1 个位置	1
3	2	接到末尾	1 2	2
4		相等，也能接到末尾	1 2 2	3
5		接到末尾	1 2 2 5	4
6	4	替换第 4 个位置	1 2 2 4
7	0	替换第 1 个位置	0 2 2 4	1

最终 $len=4$，但不能直接输出 dp 作为方案：最终的 0 2 2 4 中，数字 $0$ 在原序列的最后，无法出现在这些数之前。

dp 保存的是各个长度的最小结尾，并不是一条完整子序列。替换 dp 时，之前记录的 c[i] 保持不变。

5. 用 c 数组倒序还原方案

记录最长长度 $len$，从后往前枚举 c 数组：每遇到 $c[i]=len$，就将 $a[i]$ 压入栈，并令 $len--$，继续向前寻找新的 $len$，直到 $len=0$。最后出栈，得到正序方案。

例如：

i	1	2	3	4	5	6	7
a[i]	3	1	2	2	5	4	0
c[i]	1			3	4		1

初始 $len=4$，倒序依次找到 $c[6]=4$、$c[4]=3$、$c[3]=2$、$c[2]=1$，每选中一个数，$len$ 减 $1$。

对应的数 4 2 2 1 依次压栈，出栈得到方案 1 2 2 4。

6. 参考代码

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

const int N = 200005;
int n, a[N], dp[N], c[N], len;
stack<int> s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    dp[++len] = a[1];
    c[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (a[i] >= dp[len]) dp[++len] = a[i], c[i] = len;
        else {
            int p = upper_bound(dp + 1, dp + len + 1, a[i]) - dp;
            dp[p] = a[i];
            c[i] = p;
        }
    }
    cout << len << '\n';
    for (int i = n; i >= 1; --i) {
        if (c[i] == len) s.push(a[i]), len--;
        if (len == 0) break;
    }
    while (!s.empty()) {
        cout << s.top() << ' ';
        s.pop();
    }
    return 0;
}

每个数最多进行一次二分，时间复杂度 $O(n\log n)$；记录数组与还原方案使用 $O(n)$ 空间。输出长度后，代码中的 len 改为表示回溯时还需要寻找的长度。