簡稱LCIS，在串a和b中，有串c為串a和b的公共串，且c(i-1)<=c(i)<=c(i+1)并且c為所有公共上升子序列中最長串。

/*轉自 http://wenku.baidu.com/view/3e78f223aaea998fcc220ea0.html

定義狀態F[i][j]表示以a串的前i個字符b串的前j個字符且以b[j]為結尾構成的LCIS的長度。

為什么是這個而不是其他的狀態定義？最重要的原因是我只會這個，還有一個原因是我知道這個定義能搞到平方的算法。而我這只會這個的原因是，這個狀態定義實在是太好用了。這一點我后面再說。

我們來考察一下這個這個狀態。思考這個狀態能轉移到哪些狀態似乎有些棘手，如果把思路逆轉一下，考察這個狀態的最優值依賴于哪些狀態，就容易許多了。這個狀態依賴于哪些狀態呢？

首先，在a[i]!=b[j]的時候有F[i][j]=F[i-1][j]。為什么呢？因為F[i][j]是以b[j]為結尾的LCIS，如果F[i][j]>0那么就說明a[1]..a[i]中必然有一個字符a[k]等于b[j]（如果F[i][j]等于0呢？那賦值與否都沒有什么影響了）。因為a[k]!=a[i]，那么a[i]對F[i][j]沒有貢獻，于是我們不考慮它照樣能得出F[i][j]的最優值。所以在a[i]!=b[j]的情況下必然有F[i][j]=F[i-1][j]。這一點參考LCS的處理方法。

那如果a[i]==b[j]呢？首先，這個等于起碼保證了長度為1的LCIS。然后我們還需要去找一個最長的且能讓b[j]接在其末尾的LCIS。之前最長的LCIS在哪呢？首先我們要去找的F數組的第一維必然是i-1。因為i已經拿去和b[j]配對去了，不能用了。并且也不能是i-2，因為i-1必然比i-2更優。第二維呢？那就需要枚舉b[1]..b[j-1]了，因為你不知道這里面哪個最長且哪個小于b[j]。這里還有一個問題，可不可能不配對呢？也就是在a[i]==b[j]的情況下，需不需要考慮F[i][j]=F[i-1][j]的決策呢？答案是不需要。因為如果b[j]不和a[i]配對，那就是和之前的a[1]..a[j-1]配對（假設F[i-1][j]>0，等于0不考慮），這樣必然沒有和a[i]配對優越。（為什么必然呢？因為b[j]和a[i]配對之后的轉移是max(F[i-1][k])+1，而和之前的i`配對則是max(F[i`-1][k])+1。顯然有F[i][j]>F[i`][j],i`>i）

于是我們得出了狀態轉移方程：

a[i]!=b[j]: ? F[i][j]=F[i-1][j]?

a[i]==b[j]: ? F[i][j]=max{F[i-1][k]}+1 1<=k<=j-1&&b[j]>b[k]?

不難看到，這是一個時間復雜度為O(n^3)的DP，離平方還有一段距離。

但是，這個算法最關鍵的是，如果按照一個合理的遞推順序，max(F[i-1][k])的值我們可以在之前訪問F[i][k]的時候通過維護更新一個max變量得到。怎么得到呢？首先遞推的順序必須是狀態的第一維在外層循環，第二維在內層循環。也就是算好了F[1][len(b)]再去算F[2][1]。 如果按照這個遞推順序我們可以在每次外層循環的開始加上令一個max變量為0，然后開始內層循環。當a[i]>b[j]的時候令max=F[i-1][j]。如果循環到了a[i]==b[j]的時候，則令F[i][j]=max+1。

最后答案是F[len(a)][1]..F[len(a)][len(b)]的最大值。*/

PS: a[i] > b[j]的原因： 因為由上面的轉移有到b[j] > b[k]，當a[i] == b[j]時，我們得到a[i] > b[k]，而這個k就是在a[i] != b[j]的時候找的，也就是說 a[i] > b[j]時得到的F[i-1][j]屬于F[i-1][k]。

其實可以優化為1維的，因為F[i][j]中i是嚴格上升，可以用滾動數組。

在此基礎上壓掉了一維空間（時間還是平方）。i循環到x的時候，F[i]表示原來F[x][j]。之所以可以這樣，是因為如果a[i]!=b[j]，因為F[x][j]=F[x-1][j]值不變，F[x]不用改變，沿用過去的就好了，和這個比較維護更新得到的max值依然是我們要的。而a[i]==b[j]的時候，就改變F[x]的值好了。具體結合代碼理解。

可以得到：

a[i]>b[j]: ? Max=max{Max, F[j]}?

a[i]==b[j]: ? F[j]=Max+1

參考代碼：

    #include <iostream>

using namespace std;

#define ll long long

const int MAXN = 3005;

int max(const int& a, const int& b){return a>b?a:b;}

ll f[MAXN], a[MAXN], b[MAXN];

int n;

int main()

{

	cin >> n;

	int i, j, k;

	for(i = 1; i <= n; i++) cin >> a[i];

	for(i = 1; i <= n; i++) cin >> b[i];

	ll ans = 0, maxi = 0;;

	for(i = 1; i <= n; i++)

	{

		maxi = 0;

		for(j = 1; j <= n; j++)

			if(a[i] > b[j] && maxi < f[j]) maxi = f[j];

			else if(a[i] == b[j]) f[j] = maxi+1, ans = max(ans, f[j]); //我們在這里直接維護ans就ok

	}

	cout << ans;	

	return 0;

}
  

參考例題： http://wikioi.com/problem/1408/

最長公共上升子序列