[程式設計] 最長遞增子序列

簡介

最長遞增子序列 (Longest increasing subsequence; LIS) 是一個需要使用動態規劃 (dynamic programming) 技巧解決的問題。

這篇文章中會說明

• 何謂 LIS 問題
• 解法的設計原理
• 如何輸出 LIS 結果

這裏用的是 e-tutor 上的題目 [C_DT05-中] 尋找任意整數數列中之最大遞增子數列 為範例來解說。

何謂子序列 (subsequence) ?

要瞭解子序列，先談談何謂序列。

序列是一串元素的集合，元素可以是字串，字元，整數…等 (反正可以比大小即可)。

例如 -1,-9,2,7,0,11,-98 就是一串序列，元素用逗點隔開。

那子序列呢，就是序列的一部分囉。

例如 -1, 2, 11 是一個序列。

注意，序列中的元素可以「不連續」，但順序不能錯。

例如 -9, -1, 2，雖然它的每個元素都在 -1,-9,2,7,0,11,-98 中，但它不是一個 "-1,-9,2,7,0,11,-98" 的子序列。因為在原序列中， -9 是排在 -1 後的，但在這個序列中，-9 排在 -1 之前。

遞增子序列

遞增子序列，故名思義，就是一個子序列，裏面的每個元素都以遞增方式排序。這裏我們不使用數學來解釋，僅用簡單的例子讓你瞭解何謂遞增子序列。

還是以 -1,-9,2,7,0,11,-98 為例。

-1, 2, 7 是一個遞增子序列，因為裏面的元素是由小到大，由左而右排列。

同理， 2, 7, 11 也是一個遞增子序列。

但，-1, -9, 7 就不是遞增子序列了。因為 -1 比 -9 大，但它居然排在 -9 的左邊，那就不是遞增的排序了。

由上面的解釋也可以看到，遞增子序列有好多個。

遞增子序列的長度

子序列的長度，代表了這個子序列中元素的個數。

所以 -1, 2, 7 的長度為 3。

最長遞增子序列

把所有的子序列都列出來，裏面長度最長的那個，就是而「最長」遞增子序列囉。

以 -1,-9,2,7,0,11,-98 為例，它「最長遞增子序列 」為 -1,2,7,11。

用暴力法來解

在沒有想法的情況下，我們通常會用暴力法來解。簡單來說，就是列出所有的可能子序列，然後：

1. 檢查是否為遞增子序列
2. 儲存它的長度

最後把長度最長，且為遞增的子序列回傳即可。

那這種作法的代價為何呢？

由於每個元素都可能是子序列的一員，所以每個元素都可能「出現」，或「不出現」在子序列中。

透過上述的分析，有 n 個元素，那子序列的個數為 2^n，當 n 很大時，是個超級可怕的數字。

所以這題用暴力法來解的話，是不可行的。

使用動態規劃

這題有動態規劃的解法，也有不是動態規劃的解法。這篇文章使用動態規劃的解法。

底下以 -1,-9,2,7,0,11,-98 為例來說明。

我們用一個陣列來儲存最長遞增子序列的「長度」。假設這個陣列叫 LISTbl 好了。

另外，我就用 LIS 代表「最長遞增子序列」這幾個字了。

LISTbl[i] 就是以第 i 個元素為「結尾」的最長遞增子序列的長度！這個敘述聽完腦筋會打結，所以還是用例子來說明。

• 假設 i 為 3，那第 i 個元素就是 7。
• 所以 LISTbl[3] 就代表以 7 為「結尾」的最長遞增子序列的長度 (請見下圖)

看完後，你應該會有底下的疑問。

• 以某元素為結尾的 LIS 是什麼？
• 為什麼要用「結尾」來定義？
• 如何找到以某元素為結尾的 LIS ？

底下一個一個解答。

以某元素為結尾 LIS 是什麼？

還是舉例說明，以 7 結尾的 LIS 共有兩個，如下圖所示。

這兩個的長度都為 3。

可以看出，LIS 的個數不唯一囉，可能會有多個。

為什麼要用結尾來定義？

首先，我們知道任何 LIS，一定會有一個結尾，對吧？

第二，這樣的定義，可以幫我們想出解法來。怎麼說呢，請看下去。

如何找出以某元素為結尾的 LIS？

在說明前，先定義一些符號，這樣底下的文字會精簡些，你也會比較懂。

定義 LIS(i) 為一個 LIS，它的結尾是 LISTbl[i] 這個元素。

舉例， LISTbl[3] == 7，所以 LIS(3) 就是以 7 為結尾的 LIS。

那就是 -1, 2, 7 以及 -9, 2, 7 囉！

雖然我們還不知道怎麼找到 LIS(3)，但我們知道，LIS(3) 和 LIS(2)，LIS(1) 以及 LIS(0) 有關。

這是說，如果我們已經知道 LIS(2)、LIS(1)，以及 LIS(0)，那我們就可以用這些資訊，湊出 LIS(3) 了。有點弄糊了嗎？看下圖。

上圖中 LIS(2) 有兩個，分別是 -1,2 以及 -9,2，配上 7 後，就是 -1, 2, 7 以及 -9, 2, 7了。

LIS (0) 就只有 -1 自己，再加上 7，就是 -1, 7。

LIS (1) 要多一點解釋。 LISTbl[1] 為 -9。 -9 可以和 -1 接嗎？

-1, -9 是一個子序列，但不是遞增子序列，所以「不可以」。

所以 LIS(1) 只能是 -9 一個元素。再配上 7，就成為 -9, 7 囉。

所以 {-1, 2, 7}、{-9, 2, 7}、{-1, 7} 以及 {-9, 7} 比一下長度，看誰最長，就知道 LIS(3) 為 {-1, 2, 7} 以及 {-9, 2, 7}。

遞迴，遞迴！

透過前面的說明，可以看出來，LIS(3) 這個問題，和 LIS(0)，LIS(1) 以及 LIS(2) 相關，只要能解出這三個「子問題」，那 LIS(3) 就解出來了。

但你可能會大喊，我又不知道 LIS(2) 是什麼？

沒關係，LIS(2) 可以用 LIS(0)，以及 LIS(1) 解出來。

於是，你又知道 LIS(1) 可以用 LIS(0) 解出。

推到最後面， LIS(0)…因為前面沒有任何元素了，所以這是最簡單的子問題。LIS(0) 就是 LISTbl[0] 元素自己，以本例而言，就是 -1 了！

這就是遞迴關係囉！

還差一點！

還差一點就可以開始寫程式了。

在前面的說明，你可能會以為，要解 LIS(i) 時，就是把 LISTbl[i] 這個元素，配上 LIS(0), LIS(1)，LIS(2)，…，LIS(i-1) 即可。

其實「不一定」配得上喔！我們用 LIS(1) (下圖) 來解釋。

要找出 LIS(1)，就要使用 LIS(0)。 LIS(0) 如上圖所示。第 1 個元素是 -9，所以直覺上會把 -9 配上 -1，所以就是 -1, -9。但這樣不是個「遞增」子序列。所以不能這樣配！

因此 LIS(1) 只能維持自己本身囉 (即 -9)。

撰寫程式

底下展示了LIS 的程式碼，請注意，這是第一版，它只能回傳 LIS 的長度。

	int LIS(vector<int>& LISTbl)
	{
	if (LISTbl.size() == 0) return 0;
	vector<int> LISLen(LISTbl.size(), 1);
	for (int i = 1; i < LISTbl.size(); i++)
	{
	for (int j = 0; j < i; j++)
	{
	if (LISTbl[j] < LISTbl[i])
	LISLen[i] = max(LISLen[i], LISLen[j] + 1);
	}
	}
	int maxlen = *max_element(LISLen.begin(), LISLen.end());
	return maxlen;
	}

view raw LIS1.cpp hosted with ❤ by GitHub

函式的一開始會接受 LISTbl 這個 vector，以本例而言，它的內容如下圖。LISLen 在初始化時，每個元素的內容都為 1。

初始化時，LISTbl 以及 LISLen 的內容

由前面的說明知道，LIS(0) 指的是以 LISTbl[0] 為結尾的 LIS。以本例來說，LIS(0) 就是 -1，其長度為 1。

所以 LISLen[0] 中所存的，就是以 -1 為結尾的 LIS 的長度。

然後我們的程式碼就依底下想法逐步擴充下去

• 用 LIS(0) 來產生 LIS(1)
• 用 LIS(0) 及 LIS(1) 來產生 LIS(2)
• 用 LIS(0)、LIS(1) 及 LIS(2) 來產生 LIS(3)
• 依此類推

程式碼的第 5 行到第 12 行便是在做這件事。底下用一個例子來解釋。

求 LIS(0)

LIS(0) 是不用求的，因為第 0 個元素前就沒有任何元素了，所以第 0 個元素不用和其他元素串接！

以 LISTbl[0] 為結尾的 LIS 就是 LISTbl[0] 本身，且它的長度為 1。

因此 LISLen[0] 為 1。

求 LIS(1)

LIS(1) 是求以 LISTbl[1] 為結尾的 LIS。

LISTbl[1] 為 -9。它的前一個元素是 -1。因為 -9 比 -1 還要小，所以無法接在 -1 後面形成一個 LIS。

所以 LIS(1) 為 -9 自己本身，且長度為 1。

求 LIS(2)

LIS(2) 是求以 LISTbl[2] (即 2) 為結尾的 LIS。最初，指標 i 放在索引為 2 的位置，j 則指向索引為 0 的位置。

因為 LISTbl[2] (即 2) 比 LISTbl[0] (即 -1) 還要大，所以 2 可以串接在 -1 後面，成為一個遞增子序列 {-1, 2}。其長度為 2，所以將 LISLen[2] 的值由 1 改為 2。

接著指標 j 移到索引 1 的位置。我們發現 2 也比 -9 大，可以串在 -9 後面，成為一個遞增子序列 {-9, 2}，其長度也為 2。因為 LISLen[2] 的內容已經是 2 了，所以不用更動值。

求 LIS(3)

用同樣的方式可以求 LIS(3)。底下的三張圖展示了第 5 行到第 12 行的運作方法，由於圖已經說明得很清楚了，因此就省略了解說。

LIS(4) - LIS(6)

LIS(4) 到 LIS(6) 可以用前述的作法得到，所以就不展開細節了。執行到最後時，LISLen 的內容如下圖所示。

LISLen 陣列中最大值為 4，代表 1, -9, 2, 7, 0, 11, -98 中的 LIS 的長度為 4。

LISLen 陣列中最終的結果。

如果只要求最長遞增子序列的「長度」，那這題就到此為止了。

但 e-tutor 的這題，更進一步要求要輸出對應的 LIS。那該怎麼輸出 LIS 呢？

輸出對應的 LIS

由前面的說明我們知道，一個序列的 LIS 不唯一，會有多個。

以我們的例子來說，這題共有兩個 LIS，分別是

• {-1, 2, 7, 11}
• {-9, 2, 7, 11}

那要輸出那一個？

這題題目給了題示，要輸出數字大者。這兩個 LIS 的內容大部分都一樣，只有最開頭的兩個元素不同 (即 -1 及 -9)。

由於 -1 大於 -9，所以輸出 -1, 2, 7, 11。

那程式要怎麼寫呢？

我網路上搜了一下，對於輸出 LIS 並沒有一個公認最好的寫法，因此就自己來做囉。

我的作法分兩部分。

1. 找到 LIS 尾巴元素所在的位置：以這個例子來說，就是要找到 11 這個元素的位置。
2. 由尾巴元素的位置往前掃，找出其餘的每個元素：以這題來說，就是由 11 所在的位置往前掃，抓到 7，2，(-1, 9)。-1 及 9 用括號括起來的原因是因為它們兩個的 LISLen 的值都是 1，屬於同一個位階。

底下就一一說明。

找到 LIS 尾巴元素所在的位置

這個尾巴元素要符合兩個特性：

1. 它的 LISLen 的值「最大」
2. 如果有其他的元素，其 LISLen 的值跟它一樣，那就比 LISTbl 的值，最大者是我們的目標

在 1, -9, 2, 7, 0, 11, -98  的例子中，11 的 LISLen 最大，所以它就是我們的目標。

但以1,2,2,3,1,8,7,5,4 為例，8，7，5，及 4 的LISLen 都是 4，所以要比它的 LISTbl 的值，這時就是 8 勝出了 (見下圖)。

 所以 8 所在的位置為 5，因此 5 就是我們在這階段要找出的結果。

找出 LIS 的其餘元素

同樣用上一個例子來解說，我們在上一輪中，找到最尾巴的元素 8 後，下一個元素就是 3 (見下圖)，它有底下的特性。

1. 數字要比 8 小
2. 對應的 LISLen 要為 3
3. 位置排在 8 之前
4. 這個元素是所有 LISLen 為 3 的元素中最大的

再來是找 LISLen 為 2 的元素，同樣的，它符合底下的特性：

1. 數字比 3 小
2. 對應的 LISLen 為 2
3. 位置排在 3 前
4. 這個元素是所有 LISLen 為 2 的元素中最大的

相信這樣分析後，應該就可以寫出對應的程式碼。

我們說明函式所傳入的參數的意義：

1. LISTbl：LISTbl 陣列，記錄了所要找 LIS 串列
2. LISLen：記錄每個元素對應的 LIS 長度
3. tNum：所要找的數字，要比Num 小
4. tLen：所要找的數字，其對應的 LISLen 要等於 tLen
5. tStart：所要找的數字，要位置 tStart 之前
6. &Pos：回傳找到的位置
7. &Num：回傳找到的數字

程式碼如下

	void getMaxElementAndPos(vector<int>& LISTbl,
	vector<int>& LISLen, int tNum, int tlen,
	int tStart,
	int & num, int & pos)
	{
	int max = numeric_limits<int>::min();
	int maxPos;
	for (int i = tStart; i >= 0; i--)
	{
	if (LISLen[i] == tlen && LISTbl[i] < tNum)
	{
	if (LISTbl[i] > max)
	{
	max = LISTbl[i];
	maxPos = i;
	}
	}
	}
	num = max;
	pos = maxPos;
	}

view raw LIS2.cpp hosted with ❤ by GitHub

用一個例子來解釋上述的程式碼

在上圖中，如果我們要找 3 這個元素，因為 3 是接在 8 後面，且對應的長度為 3，那我們的呼叫方式如下

getMaxElementAndPos(LISTbl, LISLen, 8, 3, 5, num, pos);

上述的 5 是 8 這個元素在 LISTbl 中的索引值。

另外，程式碼中的 numeric_limits<int>::min() 則是可以取得整數的最小值。在我的電腦上，這個值是 -2147483648。

同樣的，numeric_limits<int>::max() 則是取得整數的最大值。在我的電腦上，這個值是 2147483647。

在呼叫這個函式時，記得 include<limits> 這個標頭檔。

完整版

最後，我們修改原本的 LIS 函式，讓它可以輸出 LIS 的內容。

	int LIS(vector<int>& LISTbl)
	{
	if (LISTbl.size() == 0) return 0;
	vector<int> LISLen(LISTbl.size(), 1);
	for (int i = 1; i < LISTbl.size(); i++)
	{
	for (int j = 0; j < i; j++)
	{
	if (LISTbl[j] < LISTbl[i])
	LISLen[i] = max(LISLen[i], LISLen[j] + 1);
	}
	}
	int maxlen = *max_element(LISLen.begin(), LISLen.end());
	int num, pos;
	vector<int> buf;
	getMaxElementAndPos(LISTbl, LISLen,
	numeric_limits<int>::max(),
	maxlen, LISTbl.size() - 1, num, pos);
	buf.push_back(num);
	for (int len = maxlen - 1; len >= 1; len--)
	{
	int tnum = num;
	int tpos = pos;
	getMaxElementAndPos(LISTbl, LISLen,
	tnum, len, tpos - 1, num, pos);
	buf.push_back(num);
	}
	reverse(buf.begin(), buf.end());
	for (int k = 0; k < buf.size(); k++)
	{
	if (k == buf.size() - 1)
	cout << buf[k] << endl;
	else
	cout << buf[k] << ",";
	}
	return maxlen;
	}

view raw LIS3.cpp hosted with ❤ by GitHub

程式碼 15-37 行為新增的部分。

17-19 行用來取得 LIS 的最尾巴的元素。取得後，這個元素被推入 buf 中。

21-28 行則是用來取得其餘的元素。

29-36 行則是輸出 LIS。

結語

找出 LIS 的長度本身不難，但找出 LIS 本身就複雜一點。或者你可以試試其它的方式，看有沒有更精簡的寫法。

如果你想做更多的練習，可以參考底下的題目

• [DP43-中] longest increasing subsequence (e-tutor 上的題目，單純輸出 LIS 長度，算是簡單題) 
• 300. Longest Increasing Subsequence (LeetCode 的題目，也是輸出 LIS 的長度，和上題幾乎一模一樣)
• [C_DP23-中] 最大單調遞減數字子序列 (e-tutor 上的題目，遞增改為遞減，但思考方式不變。這題要輸出 LIS 的結果，可以使用本文所使用的技巧完成)

最後，這裏是本題的 Github 庫，給大家參考。