最长公共上升子序列

题目描述

给定长度分别为 $n$、$m$ 的两个整数序列 $a$、$b$，求它们的最长公共上升子序列的长度。

选出的序列需要同时满足：

• 是两个序列的公共子序列：可以不连续，但相对顺序不变。
• 元素严格递增：后一个数必须大于前一个数。

若没有公共元素，输出 $0$。

输入格式

第一行两个整数 $n,m$，接下来两行分别包含 $n$ 个和 $m$ 个整数，表示序列 $a$、$b$。

输出格式

输出一个整数，表示最长公共上升子序列的长度。

数据范围

$1\le n,m\le3000$，$|a[i]|,|b[j]|\le10^9$，元素可以重复。

样例输入

4 4
3 1 2 4
1 3 2 4

样例输出

3

公共上升子序列 1 2 4 的长度为 $3$。

状态与转移

为了判断能否接上一个更大的数，需要固定结尾。

设 $dp[i][j]$ 表示：从 $a$ 的前 $i$ 个数中选取，与 $b$ 构成的、以 $b[j]$ 结尾的公共上升子序列的最长长度。不存在时记为 $0$。

• 不选 $a[i]$：保留 $dp[i-1][j]$。
• 选 $a[i]$：必须有 $a[i]=b[j]$，再接在一个结尾小于它的状态后面。前一个结尾位置 $k$ 必须满足 $k<j$ 且 $b[k]<b[j]$。

因此，先令 $dp[i][j]=dp[i-1][j]$；若 $a[i]=b[j]$，再更新：

$$dp[i][j]=\max\left(dp[i][j],\ 1+\max_{\substack{k<j\\b[k]<b[j]}}dp[i-1][k]\right).$$

其中，内层没有可选状态时最大值取 $0$，表示由当前元素单独组成长度为 $1$ 的序列。

直接枚举 $i,j,k$，时间复杂度为 $O(nm^2)$。

用前缀最大值优化

固定 $i$，从左到右枚举 $j$，用 mx 维护已经经过的位置中，满足 $b[k]<a[i]$ 的 $dp[i-1][k]$ 的最大值。

• 若 $b[j]<a[i]$，用 $dp[i-1][j]$ 更新 mx。
• 若 $b[j]=a[i]$，用 mx + 1 更新 $dp[i][j]$。

例如，处理样例中的 $a[4]=4$ 时：

b：           1 3 2 4
上一行 dp：   1 1 2 0

扫描前三个位置，mx 依次为 $1,1,2$；遇到最后的 $4$，便得到 $dp[4][4]=2+1=3$，对应 1 2 4。

每行开始时令 mx = 0，所有 $dp$ 初始为 $0$。答案是 $\max\limits_{1\le j\le m}dp[n][j]$，因为最优序列不一定以 $b[m]$ 结尾。

参考代码

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

const int N = 3005;
int n, m, a[N], b[N], dp[N][N];

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

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

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

    int ans = 0;
    for (int j = 1; j <= m; ++j) ans = max(ans, dp[n][j]);
    cout << ans << '\n';
    return 0;
}

时间复杂度 $O(nm)$，空间复杂度 $O(nm)$。