這題有點(diǎn)復(fù)雜的，卡了很久。在做這題以前，首先回顧一下最長(zhǎng)公共子序列（LCS）的求法：
https://blog.csdn.net/wangdan11111/article/details/41321277
上述第二種方法其實(shí)用的是記憶化搜索。

下面來(lái)討論怎么求最長(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)度。

• 那么，來(lái)看看遞推關(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 那么就說(shuō)明 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])的值我們可以在之前訪問(wèn) d[i][k] 的時(shí)候通過(guò)維護(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è)例子，可以幫助理解。