最长上升子序列 朴素版

#include <bits/stdc++.h>
#define int long long 
#define rep(i,a,n) for(int i =a;i<=n;i++)
#define per(i,a,n) for(int i =n;i>=a;i--)
#define fs first
#define sc second

using namespace std;
int f[1005];
int a[1005];
signed main(){
    int n;
    cin>>n;
    rep(i,1,n) cin>>a[i];

    rep(i,1,n){
      f[i]  = 1;
      rep(j,1,i-1){
        if(a[i]>a[j])
        f[i] = max(f[i],f[j]+1);
      }
    }
    int ans = 0;
    rep(i,1,n) ans = max(ans,f[i]);
    cout<<ans<<endl;
}

最长上升子序列 保存序列 倒序的

#include <bits/stdc++.h>
#define int long long 
#define rep(i,a,n) for(int i =a;i<=n;i++)
#define per(i,a,n) for(int i =n;i>=a;i--)
#define fs first
#define sc second

using namespace std;
int f[1005], a[1005],g[1005];
signed main(){
    int n;
    cin>>n;
    rep(i,1,n) cin>>a[i];

    rep(i,1,n){
      f[i]  = 1;
      g[i] = 0;
      rep(j,1,i-1){
        if(a[i]>a[j]){
            //f[i] = max(f[i],f[j]+1);
            if(f[i] < f[j]+1){
                f[i] = f[j]+1;
                g[i] =j;
            }
        }
      }
    }
    int k = 1;
    rep(i,1,n)
      if(f[k]<f[i]) k=i;
    cout<<f[k]<<endl;
    for(int i = 0,len = f[k];i<len;i++){
      printf("%d ",a[k]);
      k = g[k];
    }
}