python/TangDou/AcWing/LIS/895_WithPrintPath.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;

int n, a[N];
int f[N];
int res, pos; // LIS最大长度  pos:最大长度是哪个下标数字提供
int pre[N];   // 记录转移的前序关系

// ① 循环+vector打印路径
void print(int k) {
    vector<int> path; // 因为查找的关系是逆序的，需要用一个向量数组把这个逆序反过来，才能输出
    while (k) {
        path.push_back(a[k]);
        k = pre[k];
    }
    // 倒序输出LIS序列
    for (int i = path.size() - 1; i >= 0; i--) printf("%d ", path[i]);
}

// ② 递归打印路径
void out(int k) {
    if (pre[k]) out(pre[k]); // 因为最前面的第1号，它的前序
    printf("%d ", a[k]);
}

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

    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[i] > a[j] && f[i] <= f[j]) {
                f[i] = f[j] + 1;
                pre[i] = j; // f[i]的前序是f[j]
            }

        // 更新最大值
        if (f[i] > res) {
            res = f[i]; // 记录LIS最大值
            pos = i;    // 记录LIS最大值时相应的数组下标i
        }
    }

    // 输出LIS最大长度
    printf("%d\n", res);

    // 循环
    print(pos);

    puts("");
    // 递归
    out(pos);

    return 0;
}