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

算法时间复杂度改进思路主要从优化第三层（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]

poj 2127 至于要求具体子序列时，需要记录使之更新的前驱，即path[i][j]=某个位置bj； 因为是“以j结尾”，所以记录bj。输出时输出b[bj]；

详见代码： ai,aj记录使答案成为ans的第一个位置。 故可以直接输出b[aj];

#include
     
      #include
      
       #include
       
        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]
        
         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
         
          -1)        {            ans[tmp--]=b[aj];            aj=path[ai][aj];            }        ai--;       }    for(int i=1;i<=sum;i++)     printf("%d ",ans[i]);    return 0;}
         
        
       
      
     

纯手打。 参考：