最长公共子上升序列

形式化题目

给定两个整数序列 $A$ （长度 $n$ ）和 $B$ （长度 $m$ ），求一个最长的序列 $S$ ，使得：

$S$ 是 $A$ 的子序列；
$S$ 是 $B$ 的子序列；
$S$ 严格递增。

输出 $|S|$ 以及 $S$ 本身（任意一个合法的最长序列均可）。

正解

思路

设 $f[j]$ 表示以 $B[j]$ 结尾的最长上升公共子序列（LCIS）的长度。当枚举到 $A$ 中的某个元素 $x$ 时，同时扫描 $B$ ：

若 $x > B[j]$ ，则 $B[j]$ 可以作为 $x$ 的前驱，更新当前最优前驱；
若 $x == B[j]$ ，则可以把 $x$ 接在当前最优前驱后面，得到以 $B[j]$ 结尾的更长 LCIS。

为了直接输出方案，额外维护以每个 $A[i]$ 结尾的完整序列。具体地，按 $B$ 的顺序扫描时，遇到 $A[i] < B[t]$ 就继承当前最优序列；遇到 $A[i] = B[t]$ 就把 $B[t]$ 接到该序列后，并保存到位置 $i$ 。最后在所有 $A[i]$ 的结尾序列中取最长的一个输出。

这样把朴素 $O(n^4)$ 或 $O(n^3)$ 的做法压缩成 $O(n \cdot m)$ ，空间 $O(n \cdot L)$ ，其中 $L$ 为答案长度。

代码

Python 版：

python

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 04:12
# update_at: 2026-09-30 04:12

import sys


def solve() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    n = next(it)
    a = [next(it) for _ in range(n)]
    m = next(it)
    b = [next(it) for _ in range(m)]

    # order[j] 记录以 a[j] 结尾的 LCIS：长度 + 序列本身。
    lens = [0] * n
    seqs: list[list[int]] = [[] for _ in range(n)]

    for target in b:
        cur_len = 0
        cur_seq: list[int] = []
        for j, x in enumerate(a):
            if x < target and lens[j] > cur_len:
                cur_len = lens[j]
                cur_seq = seqs[j]
            elif x == target:
                lens[j] = cur_len + 1
                seqs[j] = cur_seq + [x]

    best = max(range(n), key=lambda j: lens[j], default=-1)
    length = lens[best] if best != -1 else 0

    print(length)
    print(' '.join(map(str, seqs[best])) if best != -1 else '')


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 23:58
 * update_at: 2026-10-04 23:58
 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 505;

ll a[MAXN];    // 第一个序列 A
ll b[MAXN];    // 第二个序列 B
ll lens[MAXN]; // lens[i] 表示以 A[i] 结尾的最长上升公共子序列长度
ll pre[MAXN];  // pre[i] 记录 A[i] 在答案中的前驱下标，0 表示没有前驱
ll ans[MAXN];  // 还原出来的最长上升公共子序列

int main() {
    int n = 0, m = 0;

    if (scanf("%d", &n) != 1) {
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    scanf("%d", &m);
    for (int t = 1; t <= m; t++) {
        scanf("%lld", &b[t]);
    }

    // 逐个取出 B 中的元素作为当前要接的末尾，扫描 A 更新状态。
    for (int t = 1; t <= m; t++) {
        ll best_len = 0; // 当前 target 之前能接上的最长上升公共子序列长度
        int best_idx = 0; // 这个最长子序列在 A 中的结尾下标
        for (int i = 1; i <= n; i++) {
            if (a[i] < b[t] && lens[i] > best_len) {
                // A[i] 比当前末尾小，可以作为前驱
                best_len = lens[i];
                best_idx = i;
            } else if (a[i] == b[t]) {
                // A[i] 可以作为当前公共子序列的末尾
                lens[i] = best_len + 1;
                pre[i] = best_idx;
            }
        }
    }

    // 在所有以 A[i] 结尾的答案中找最长的
    int best = 0;
    for (int i = 1; i <= n; i++) {
        if (lens[i] > lens[best]) {
            best = i;
        }
    }

    ll length = lens[best];
    // 顺着 pre 指针从后往前填回答案
    int cnt = 0;
    int cur = best;
    while (cur != 0) {
        ans[cnt] = a[cur];
        cnt++;
        cur = pre[cur];
    }
    reverse(ans, ans + cnt);

    printf("%lld\n", length);
    for (int i = 0; i < cnt; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%lld", ans[i]);
    }
    printf("\n");

    return 0;
}

复杂度

时间复杂度： $O(n \cdot m)$ ， $n, m \leqslant 500$ 。
空间复杂度： $O(n \cdot L)$ ，其中 $L$ 为 LCIS 长度，用于保存每个位置结尾的序列。

总结

本题是 LCS 与 LIS 的结合。关键观察是把“以 $B[j]$ 结尾”作为状态，在扫描 $A$ 时用滚动变量维护最优前驱，避免枚举第三维。保存完整序列即可直接输出任意一组最长上升公共子序列。

最长公共子上升序列

目录

形式化题目

正解

思路

代码

复杂度

总结