AcWing 272. 最长公共上升子序列
原题链接
中等
作者:
哂大猫
,
2021-06-02 07:52:38
,
所有人可见
,
阅读 205
import java.util.Scanner;
public class Main {
public static void main(String agrs[]) throws Exception{
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int a[]=new int[n+1];
int b[]=new int[n+1];
for(int i=1;i<=n;i++) {
a[i]=in.nextInt();
}
for(int i=1;i<=n;i++) {
b[i]=in.nextInt();
}
//a[1~i] b[1~j]中 以b[j]结尾的公共上升子序列
int f[][]=new int[n+1][n+1];
for(int i=1;i<=n;i++) {
int maxv=1;
for(int j=1;j<=n;j++) {
//不包含a[i];
f[i][j]=f[i-1][j];
//包含a[i]
if(a[i]==b[j]) f[i][j]=Math.max(maxv, f[i][j]);
//再细分为j-1种情况 倒数第二个上升公共子序列是以0(不存在) 1 ... j-1
if(a[i]>b[j]) maxv=Math.max(maxv, f[i-1][j]+1);
}
}
int res=0;
for(int i=1;i<=n;i++) res=Math.max(res, f[n][i]);
System.out.println(res);
}
}