首页 > 代码库 > 最长公共上升子序列
最长公共上升子序列
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 }
最长公共上升子序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。