普通版与记录路径版本

参考代码：

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
int n, a[N], f[N];

// f[i]:表示以a[i]结尾的最长上升子序列长度

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[j] < a[i]) f[i] = max(f[i], f[j] + 1);
    }
    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res, f[i]);
    cout << res << endl;
    return 0;
}

简单优化：将最大值更新直接放入循环内更新

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
int n, a[N], f[N];

// f[i]:表示以a[i]结尾的最长上升子序列长度

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int res = 0;
    for(int i = 1; i <= n; i++){
        // 初始化，只有自己最长为一
        f[i] = 1;
        for(int j = 1; j < i; j++)
            if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    cout << res << endl;
    return 0;
}

记录路径代码实现：

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;
int n, a[N], f[N];

// 额外拓展：记录最长上升子序列路径
// 只需要记录当前状态是哪个状态转移过来的即可！
int g[N];

// f[i]:表示以a[i]结尾的最长上升子序列长度

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++){
        // 初始化，只有自己最长为一
        f[i] = 1;
        // 记录路径初始化：表示是第一个数
        g[i] = 0;
        for(int j = 1; j < i; j++)
            // if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
            // 修改如下：
            if(a[j] < a[i]){
                // 前面状态更优
                if(f[i] < f[j] + 1){
                    // 更新f[i]
                    f[i] = f[j] + 1;
                    // 更新g[i]表示当前状态由a[j]转移而来
                    g[i] = j;
                }
            }
    }
    // int res = 0;
    // for(int i = 1; i <= n; i++) res = max(res, f[i]);
    // cout << res << endl;
    // 修改如下：
    int k = 1;
    for(int i = 1; i <= n; i++)
        if(f[k] < f[i]) k = i;
    cout << a[k] << endl;
    // 状态倒序输出
    int len = f[k];
    while(len --){
        cout << a[k] << " ";
        k = g[k];
    }
    return 0;
}