这题有点复杂的，卡了很久。在做这题以前，首先回顾一下最长公共子序列（LCS）的求法：
https://blog.csdn.net/wangdan11111/article/details/41321277
上述第二种方法其实用的是记忆化搜索。
下面来讨论怎么求最长公共上长子序列（LCIS）
令两个数列保存于a[]和b[]，长度分别为n和m
首先，定义状态d[i][j]：以a数组的前i个元素，b数组的前j个元素并且以b[j]为结尾的LCIS的长度。
-
那么，来看看递推关系是怎么样的：
当 a[i] ！= b[j] 时， d[i][j] = d[i-1][j]; 因为 d[i][j] 是以 b[j] 为结尾的LCIS，如果 d[i][j] > 0 那么就说明 a[1] .... a[i] 中必然有一个元素 a[k] 等于 b[j]。因为 a[k] != a[i]，那么 a[i] 对 d[i][j] 没有贡献，于是我们不考虑它照样能得出 d[i][j] 的最优值。所以在 a[i] != b[j] 的情况下必然有 d[i][j] = d[i-1][j]。这一点参考LCS的处理方法。d[i][j]=d[i-1][j];当 a[i] == b[j] 时， 这个等于起码保证了长度为1的LCIS。然后我们还需要去找一个最长的且能让b[j]接在其末尾的LCIS。之前最长的LCIS在哪呢？首先我们要去找的d数组的第一维必然是i-1。因为i已经拿去和b[j]配对去了，不能用了。第二维需要枚举 b[1] ... b[j-1]了，因为你不知道这里面哪个最长且哪个小于 b[j]。
所以状态转移方程：d[i][j]=max(d[i-1][k]) + 1; （1<= k <= j-1 且 b[k]<b[j]） 最后要求的就是d[n][1],d[n][2],...,d[n][m]的最大值，然后用一个pre[]记录前一个位置，递归输出其中一个满足要求的子序列即可，代码如下：
//不能在最长公共子序列中求最长上升子序列，反例如下：
//1 6 3 4 8 和 1 3 6 4 8
//最长公共子序列：1 6 4 8
//最长公共上升子序列：1 3 4 8,不在上述求出的序列中
#define debug(x) std::cerr<<#x<<" = "<<(x)<<std::endl;
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,a[501],b[501],d[501][501],pre[501];
void print(int x){
if (x==0) return;
print(pre[x]);
printf("%d ",b[x]);
}
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)
for (int j=1;j<=m;++j){
d[i][j]=d[i-1][j];
if (a[i]==b[j]){
int maxn=0,ind=0;
for (int k=1;k<=j-1;++k)
if (d[i-1][k]>maxn && b[k]<b[j]){
maxn=d[i-1][k];
ind=k;
}
d[i][j]=maxn+1;
pre[j]=ind;
}
}
int ans=0,ind=0;
for (int j=1;j<=m;++j)
if (ans<d[n][j]){
ans=d[n][j];
ind=j;
}
cout<<ans<<endl;
print(ind);
cout<<endl;
return 0;
}
不难看到，这是一个时间复杂度为O(n^3)的DP，离平方还有一段距离。
但是，这个算法最关键的是，如果按照一个合理的递推顺序，max(d[i-1][k])的值我们可以在之前访问 d[i][k] 的时候通过维护更新一个max变量得到。怎么得到呢？首先递推的顺序必须是状态的第一维在外层循环，第二维在内层循环。也就是算好了 d[1][m] 再去算 d[2][1]。 如果按照这个递推顺序我们可以在每次外层循环的开始加上令一个max变量为0，然后开始内层循环。当a[i]>b[j]的时候令max = d[i-1][j]。如果循环到了a[i] == b[j]的时候，则令 d[i][j] = max+1。 最后答案是 d[n][1] ... d[n][m]的最大值。
上述分析参考了：https://www.cnblogs.com/wd-one/p/4470844.html
里面还有一个例子，可以帮助理解。
