LICS：最长公共上升子序列；
一般令f[i][j]表示a串前i位，b串以j结尾的LICS长度。于是，答案为：max(1~m)(f[n][i]);
朴素做法：O(n^3) 相等时，从1~j-1枚举最大值。
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {if(a[i]!=b[j]) f[i][j]=f[i-1][j]; else if(a[i]==b[j]) for(int k=1;k<j;k++) if(b[k]<b[j]) f[i][j]=f[i-1][k]; }
算法时间复杂度改进思路主要从优化第三层（k）复杂度入手。
升级做法: O(n^2logn) 利用树状数组记录f[i-1][1~j-1]最大值； 数组下表记录的是b串数值。 （第一个j循环预处理，并且更新上一次的成果）需要：树状数组和离散化。
int mx[] for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) {mx[j]=query(b[j]-1)//0~b[j]-1 这些数中的f最大值 modify(b[j],f[i-1][j])//将上一轮求出的f尝试更新 } for(int j=1;j<=m;j++) if(a[i]==b[j]) f[i][j]=mx[j]+1; else f[i][j]=f[i-1][j]; }
其实这样很麻烦。 复杂度中等，还需要离散化，求具体子序列还要还原。
终极做法：O(n^2) 考虑到，每次进行j循环时，i不动，a[i]的值暂时不变。所以只需边求边记录最大值即可。 直接省掉k层循环。
for(int i=1;i<=n;i++) { int mx=f[i-1][0]; for(int j=1;j<=m;j++) if(a[i]!=a[j]) f[i][j]=f[i-1][j] else f[i][j]=mx+1; if(b[j]<a[i])//j即将变成j+1，尝试更新mx（只有b[j]<a[i]才可以保证上升） mx=max(mx,f[i-1][j]) }
poj 2127 至于要求具体子序列时，需要记录使之更新的前驱，即path[i][j]=某个位置bj； 因为是“以j结尾”，所以记录bj。输出时输出b[bj]；
详见代码： ai,aj记录使答案成为ans的第一个位置。 故可以直接输出b[aj];
#include<cstdio> #include<cstdlib> #include<iostream> using namespace std; const int N=505; int f[N][N],path[N][N]; int mj,mx,sum,ai,aj; int ans[N]; int n,m; int a[N],b[N]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); for(int i=1;i<=m;i++) scanf("%d",&b[i]); for(int i=1;i<=n;i++) { mx=0; for(int j=1;j<=m;j++) { f[i][j]=f[i-1][j]; path[i][j]=-1; if(b[j]<a[i]&&f[i-1][j]>mx) { mx=f[i-1][j]; mj=j; } else if(a[i]==b[j]) { f[i][j]=mx+1; path[i][j]=mj; } if(sum<f[i][j]) { sum=f[i][j]; ai=i; aj=j; } } } printf("%d ",sum); int tmp=sum; while(tmp) { if(path[ai][aj]>-1) { ans[tmp--]=b[aj]; aj=path[ai][aj]; } ai--; } for(int i=1;i<=sum;i++) printf("%d ",ans[i]); return 0; }
纯手打。 参考：https://www.cnblogs.com/dream-wind/archive/2012/08/25/2655641.html