思路

二次DP恢复任意最优子序列，使用验证性质的特殊判题器。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;vector<long long>a(n);for(auto &x:a)cin>>x;vector<int>d(n,1),pre(n,-1);int best=0;for(int i=0;i<n;i++){for(int j=0;j<i;j++)if(a[j]<=a[i]&&d[j]+1>d[i]){d[i]=d[j]+1;pre[i]=j;}if(d[i]>d[best])best=i;}vector<long long>out;for(int i=best;i!=-1;i=pre[i])out.push_back(a[i]);reverse(out.begin(),out.end());cout<<"max="<<out.size()<<'\n';for(int i=0;i<(int)out.size();i++){if(i)cout<<' ';cout<<out[i];}cout<<'\n';}