首页 > 代码库 > 最长公共上升子序列(LICS) 模板
最长公共上升子序列(LICS) 模板
1 void LICS() 2 { 3 for (int i=1;i<=n;i++) 4 { 5 int ma=0; 6 for (int j=1;j<=n;j++) 7 { 8 if (a[i]==b[j]) 9 f[i][j]=ma+1;10 else f[i][j]=f[i-1][j];11 if (b[j]<a[i] && f[i-1][j]>ma)12 ma=f[i-1][j];13 ans=max(ans,f[i][j]);14 }15 }16 printf("%d\n",ans);17 }
空间优化到一维：
1 void LICS() 2 { 3 for (int i=1;i<=n;i++) 4 { 5 int ma=0,tmp; 6 for (int j=1;j<=n;j++) 7 { 8 tmp=ma; 9 if (b[j]<a[i] && f[j]>ma)10 ma=f[j];11 if (a[i]==b[j])12 f[j]=tmp+1;13 ans=max(ans,f[j]);14 }15 }16 printf("%d\n",ans);17 }
最长公共上升子序列(LICS) 模板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。