最长公共上升子序列

 1 #include<cstdio>
 2 int m,n,ans(0),i1[3001],i2[3001],f[3001][3001]={0}; //二维。
 3 int main()
 4 {
 5     scanf("%d",&m);
 6     scanf("%d",&n); 
 7     for (int a=1;a<=m;a++)
 8       scanf("%d",&i1[a]);
 9     for (int a=1;a<=n;a++)
10       scanf("%d",&i2[a]); 
11     for (int a=1;a<=m;a++)
12     {
13         int max(0);
14         for (int b=1;b<=n;b++)
15         {
16           if (i1[a]>i2[b]&&f[a-1][b]>max) //在寻找上升序列的同时，存储其最大成功值。 
17             max=f[a-1][b];
18           if (i1[a]!=i2[b]) //如不相等，则无变化。 
19             f[a][b]=f[a-1][b];
20           if (i1[a]==i2[b]) //若相等，在最大值基础上+1。 
21             f[a][b]=max+1;
22         }
23     }
24     for (int a=1;a<=n;a++)
25       ans=ans>f[m][a]?ans:f[m][a]; //已传值到底部，遍历寻找最大值，即为所求。 
26     printf("%d",ans);
27 return 0;
28 }