LICS O（n*m）+前驱路径
枫林晚
2018-03-27 16:15:57
LICS：最长公共上升子序列；
一般令f[i][j]表示a串前i位，b串以j结尾的LICS长度。于是，答案为：max(1~m)(f[n][i]);
朴素做法：O(n^3)
相等时，从1~j-1枚举最大值。
```cpp
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循环预处理，并且更新上一次的成果）需要：树状数组和离散化。
```cpp
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层循环。
```cpp
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][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\n",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