LIS,LCS,LCIS

#include<iostream>
using namespace std;
int a[1100],dp[1100],ans,n;
int main() {
  cin>>n;
  for(int i=1; i<=n; i++) {
    cin>>a[i];
    dp[i]=1;//初始状态
  }
  ans=1;
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=i; j++) {
      if(a[j]<a[i]) {
        dp[i]=max(dp[i],dp[j]+1);//状态转移
        ans=max(ans,dp[i]);
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

#include<iostream>
using namespace std;
int a[1100],dp[1100],ans,n;
int main() {
  cin>>n;
  for(int i=1; i<=n; i++) {
    cin>>a[i];
    dp[i]=1;//初始状态
  }
  ans=1;
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=i; j++) {
      if(a[j]<a[i]) {
        dp[i]=max(dp[i],dp[j]+1);//状态转移
        ans=max(ans,dp[i]);
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

#include<iostream>
#include<string.h>
using namespace std;
const int N=1010;
int n,m;
int a[N],b[N];
int f[N][N];
int main() {
  int t;
  cin>>t;
  while(t--) {
    memset(f,0,sizeof(f));
    cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;for(int i=1;i<=m;i++)cin>>b[i];
    for(int i=1; i<=n; i++) {
      int maxv=1;
      for(int j=1; j<=m; j++) {
        f[i][j]=f[i-1][j];
        if(a[i]==b[j])
          f[i][j]=max(f[i][j],maxv);
        if(b[j]<a[i])
          maxv=max(maxv,f[i-1][j]+1);
      }
    }
    int res=0;
    for(int i=1;i<=m;i++){
      res=max(res,f[n][i]);
    }
    cout<<res<<endl;
    if(t!=0){
      cout<<endl;
    }
  }
}