最长公共上升子序列 LCIS
给你两个长度为n的数组。让你求它们的最长公共上升子序列。 in: 4 2 2 1 3 2 1 2 3 out: 2
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int a[3005], b[3005], f[3005][3005];
int main()
{
int n; scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
}
for(int i=1; i<=n; i++){
scanf("%d", &b[i]);
}
for(int i=1; i<=n; i++){
int mx=0;
for(int j=1; j<=n; j++){
f[i][j]=f[i-1][j];//初始化
if(a[i]>b[j]) mx=max(mx, f[i-1][j]);
if(a[i]==b[j]) f[i][j]=mx+1;
}
}
int ans=0;
for(int i=1; i<=n; i++){
ans=max(ans, f[n][i]);
}
printf("%d\n", ans);
return 0;
}
