思路与算法

按第一序列逐个元素，扫描第二序列；固定第二序列终点的LCIS长度，在较小值位置维护上一行最大长度，遇到相等值可接长，并保存二维回溯来源。

正确性说明

以第二序列b[j]结尾的公共上升序列，要么不使用当前a[i]而继承旧状态，要么a[i]=b[j]并接到此前b[t]<a[i]的最佳状态。递增扫描保证t<j，读取上一行保证第一序列下标也递增。回溯每次降一行并沿较小值来源，得到合法最优公共子序列。

复杂度

O(NM)时间与O(NM)空间，含状态/回溯表初始化；输出长度至多min(N,M)。

易错点

严格上升，不允许相等值接长；空公共序列输出0及空行。整数包括int32最小值，比较不做相减。多解按合法性与最优长度判定。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DS {
    vector<int> p, s;
    DS(int n) : p(n), s(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int u) {
        while (p[u] != u) {
            p[u] = p[p[u]];
            u = p[u];
        }
        return u;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (s[a] > s[b])
            swap(a, b);
        p[a] = b;
        s[b] += s[a];
        return true;
    }
};

int main() {
    int n, m;
    cin >> n;
    vector<long long> a(n), b;
    for (auto &x : a)
        cin >> x;
    cin >> m;
    b.resize(m);
    for (auto &x : b)
        cin >> x;
    vector<vector<int>> d(n + 1, vector<int>(m)), pre(n + 1, vector<int>(m, -1));
    for (int i = 1; i <= n; i++) {
        int best = 0, at = -1;
        for (int j = 0; j < m; j++) {
            d[i][j] = d[i - 1][j];
            if (b[j] < a[i - 1] && d[i - 1][j] > best) {
                best = d[i - 1][j];
                at = j;
            }
            if (b[j] == a[i - 1] && best + 1 > d[i][j]) {
                d[i][j] = best + 1;
                pre[i][j] = at;
            }
        }
    }
    int at = max_element(d[n].begin(), d[n].end()) - d[n].begin(), len = d[n][at];
    cout << len << "\n";
    vector<long long> out;
    for (int i = n; i && len; i--)
        if (pre[i][at] != -1 || d[i][at] > d[i - 1][at]) {
            out.push_back(b[at]);
            at = pre[i][at];
            len--;
        }
    reverse(out.begin(), out.end());
    for (auto x : out)
        cout << x << " ";
    cout << "\n";
}