這題有點(diǎn)復(fù)雜的主守，卡了很久禀倔。在做這題以前榄融，首先回顧一下最長(zhǎng)公共子序列（LCS）的求法：
https://blog.csdn.net/wangdan11111/article/details/41321277
上述第二種方法其實(shí)用的是記憶化搜索。
下面來討論怎么求最長(zhǎng)公共上長(zhǎng)子序列（LCIS）
令兩個(gè)數(shù)列保存于a[]和b[]救湖，長(zhǎng)度分別為n和m
首先愧杯，定義狀態(tài)d[i][j]：以a數(shù)組的前i個(gè)元素，b數(shù)組的前j個(gè)元素并且以b[j]為結(jié)尾的LCIS的長(zhǎng)度鞋既。
-
那么力九，來看看遞推關(guān)系是怎么樣的：
當(dāng) a[i] ！= b[j] 時(shí)涛救， d[i][j] = d[i-1][j]; 因?yàn)?d[i][j] 是以 b[j] 為結(jié)尾的LCIS畏邢，如果 d[i][j] > 0 那么就說明 a[1] .... a[i] 中必然有一個(gè)元素 a[k] 等于 b[j]。因?yàn)?a[k] != a[i]检吆，那么 a[i] 對(duì) d[i][j] 沒有貢獻(xiàn)舒萎，于是我們不考慮它照樣能得出 d[i][j] 的最優(yōu)值。所以在 a[i] != b[j] 的情況下必然有 d[i][j] = d[i-1][j]蹭沛。這一點(diǎn)參考LCS的處理方法臂寝。d[i][j]=d[i-1][j];當(dāng) a[i] == b[j] 時(shí)， 這個(gè)等于起碼保證了長(zhǎng)度為1的LCIS摊灭。然后我們還需要去找一個(gè)最長(zhǎng)的且能讓b[j]接在其末尾的LCIS咆贬。之前最長(zhǎng)的LCIS在哪呢？首先我們要去找的d數(shù)組的第一維必然是i-1帚呼。因?yàn)閕已經(jīng)拿去和b[j]配對(duì)去了掏缎，不能用了。第二維需要枚舉 b[1] ... b[j-1]了煤杀，因?yàn)槟悴恢肋@里面哪個(gè)最長(zhǎng)且哪個(gè)小于 b[j]眷蜈。
所以狀態(tài)轉(zhuǎn)移方程：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]的最大值，然后用一個(gè)pre[]記錄前一個(gè)位置沈自，遞歸輸出其中一個(gè)滿足要求的子序列即可酌儒，代碼如下：
//不能在最長(zhǎng)公共子序列中求最長(zhǎng)上升子序列，反例如下：
//1 6 3 4 8 和 1 3 6 4 8
//最長(zhǎng)公共子序列：1 6 4 8
//最長(zhǎng)公共上升子序列：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;
}
不難看到枯途，這是一個(gè)時(shí)間復(fù)雜度為O(n^3)的DP忌怎，離平方還有一段距離。
但是酪夷，這個(gè)算法最關(guān)鍵的是榴啸，如果按照一個(gè)合理的遞推順序，max(d[i-1][k])的值我們可以在之前訪問 d[i][k] 的時(shí)候通過維護(hù)更新一個(gè)max變量得到晚岭。怎么得到呢插掂？首先遞推的順序必須是狀態(tài)的第一維在外層循環(huán)，第二維在內(nèi)層循環(huán)。也就是算好了 d[1][m] 再去算 d[2][1]辅甥。 如果按照這個(gè)遞推順序我們可以在每次外層循環(huán)的開始加上令一個(gè)max變量為0，然后開始內(nèi)層循環(huán)燎竖。當(dāng)a[i]>b[j]的時(shí)候令max = d[i-1][j]璃弄。如果循環(huán)到了a[i] == b[j]的時(shí)候，則令 d[i][j] = max+1构回。 最后答案是 d[n][1] ... d[n][m]的最大值夏块。
上述分析參考了：https://www.cnblogs.com/wd-one/p/4470844.html
里面還有一個(gè)例子，可以幫助理解纤掸。
