$O(n^2)$

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int dp[1005];     // dp[i]: 以 a[i] 结尾的最长上升子序列的长度
int pre[1005];    // 最佳方案的前一个数选的是谁
vector<int> path; // 记录最终答案的方案
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 0;
    int ansi = 0; // 最长的是以哪一个位置结尾的
    for (int i = 1; i <= n; i++)
    {
        dp[i] = 1;
        // 考虑前面的位置 j
        for (int j = i - 1; j >= 1; j--)
        {
            // 如果 a[i] 可以接在 a[j] 后面构成上升子序列
            if (a[i] >= a[j])
                if (dp[j] + 1 > dp[i])
                    dp[i] = dp[j] + 1, pre[i] = j;
        }
        if (dp[i] > ans)
            ans = dp[i], ansi = i;
    }
    cout << "max=" << ans << "\n";
    // 找到方案
    int now = ansi;
    path.push_back(now);
    while (pre[now] != 0)
        path.push_back(pre[now]), now = pre[now];
    // 输出方案
    for (int i = path.size() - 1; i >= 0; i--)
        cout << a[path[i]] << " ";
    return 0;
}

$O(n\log n)$

#include<bits/stdc++.h>
using namespace std;
int a[100005],t[100005],len;
int p[100005];
int path[100005],pre[100005],cnt,now;
int n; 
int main(){
	cin>>n;
	for(int i = 1;i <= n;i++){
		cin>>a[i];
		if(a[i] >= t[len]){
			t[++len] = a[i];
			p[len] = i;
			pre[i] = p[len-1];
		}
		else{
			int pos = lower_bound(t+1,t+len+1,a[i])-t;
			t[pos] = a[i];
			p[pos] = i;
			pre[i] = p[pos-1];
		}
	}
	cout<<"max="<<len<<endl;
	now = p[len];
	while(now != 0){
		path[++cnt] = a[now];
		now = pre[now];
	}
	for(int i = cnt;i >= 1;i--) cout<<path[i]<<" ";
	return 0;
}