找到最长上升子序列并输出

#include <iostream>
#include <stack>

using namespace std;

const int N = 1010;

int a[N], dp[N], g[N];
int n;
stack<int> res;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        dp[i] = 1;
        g[i] = 0;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (a[j] < a[i]) {
                if (dp[i] < dp[j] + 1) {
                   dp[i] = dp[j] + 1;
                   g[i] = j;
                }
            }
        }
    }
    int k = 1;
    for (int i = 1; i <= n; i++)
        if (dp[k] < dp[i])
            k = i;
    cout << dp[k] << endl;

    for (int i = 1, len = dp[k]; i <= len; i++) {
        res.push(a[k]);
        k = g[k];
    }

    while(!res.empty()) {
        cout << res.top() << ' ';
        res.pop();
    }
    cout << endl;

    return 0;
}