最长公共上升子序列

 n^3

#include <iostream>
#include <algorithm>
#include<cstring>
#include <vector>
using namespace std; 
 const int N=600;
  int n,m,a[N],b[N],f[N][N];
  int r[N];
  
  void print(int i){
      if(i) print(r[i]),cout<<b[i]<<' ';
      
  }
 void solve(){
     int i,j;
     for(i=1;i<=n;i++)
       for(j=1;j<=m;j++){
           f[i][j]=f[i-1][j];
          if(a[i]==b[j]){
              int id=0;
              for(int k=1;k<j;k++){
                   if(b[j]>b[k]&&f[i-1][k]>f[i-1][id]) 
                    id=k;
              }
            f[i][j]=f[i-1][id]+1; r[j]=id;
        }
      }
    cout<<f[n][m]<<endl;
    int id=0;
    for(i=1;i<=m;i++) 
     if(f[n][i]>=f[n][id]) id=i;
    print(id); 
 }
 signed main(){
     int i;
     cin>>n;
     for(i=1;i<=n;i++) cin>>a[i];
     cin>>m;
     for(i=1;i<=m;i++) cin>>b[i];
     solve();
 }
 

  

n^2 ，只求长度

#include <iostream>
#include <algorithm>
#include<cstring>
#include <vector>
using namespace std; 
 const int N=3004;
  int n,m,a[N],b[N],f[N][N];
  
  
 void solve(){
     int i,j;
     for(i=1;i<=n;i++){
     int mx=1;
      for(j=1;j<=m;j++){
          f[i][j]=f[i-1][j];
          if(a[i]==b[j])
              f[i][j]=max(mx,f[i][j]);
          if(a[i]>b[j]) mx=max(mx,f[i-1][j]+1);
      }
    }
      int ans=0;
      for(j=1;j<=m;j++) ans=max(ans,f[n][j]);
    cout<<ans<<endl;
 }
 signed main(){
     int i;
     cin>>n;
     for(i=1;i<=n;i++) cin>>a[i];
     //cin>>m;
     m=n;
     for(i=1;i<=m;i++) cin>>b[i];
     solve();
 }