给定两个 整数序列，求LCIS(最长公共上升子序列）
dp[i][j]表示A的A[1.....i]与B[1.....j]的以B[j]为结尾的LCIS。
转移方程很简单
当A[i]!=B[j] dp[i][j]=dp[i-1][j]
else dp[i][j]=max(dp[i][k]+1) k<j A[i]>B[k]
朴素实现O（n^3）
通过标记最大值的方法可以优化到O(n^2)
代码很简单
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=500+5;
int dp[maxn][maxn];
int pre[maxn][maxn];
int A[maxn],B[maxn];
int n1,n2;
vector<int> getLcis()
{
memset(dp,0,sizeof(dp));
memset(pre,0,sizeof(pre));
vector<int>lcis;
for(int i=1;i<=n1;i++)
{
int k=0;
for(int j=1;j<=n2;j++)
{
if(A[i]!=B[j])dp[i][j]=dp[i-1][j];
if(A[i]>B[j]&&dp[i][j]>dp[i][k])k=j;
if(A[i]==B[j])
{
dp[i][j]=dp[i][k]+1;
pre[i][j]=k;
}
}
}
int ans=-1,x=n1,y=0;
for(int i=1;i<=n2;i++)
{
if(dp[n1][i]>ans)
{
ans=dp[n1][i];
y=i;
}
}
lcis.resize(ans);
int cnt=1;
while(dp[x][y])
{
if(A[x]!=B[y])x--;
else{
lcis[ans-cnt]=B[y];
cnt++;
y=pre[x][y];
}
}
return lcis;
}
int main()
{freopen("t.txt","r",stdin);
scanf("%d",&n1);
for(int i=1;i<=n1;i++)
scanf("%d",&A[i]);
scanf("%d",&n2);
for(int i=1;i<=n2;i++)
scanf("%d",&B[i]);
vector<int>L=getLcis();
printf("%d
",L.size());
for(int ii=0;ii<(int)(L.size()-1);ii++)
if(ii<L.size())printf("%d ",L[ii]);
if(L.size()>0)printf("%d
",L[L.size()-1]);
return 0;
}