Sequence

「數列」。一串數字。

例如1 3 5 2 9，由五個數字組成的數列。

「序列」。一串字元。字元其實是數字。

例如a c e b i，由五個字元組成的序列。

Subsequence

「子序列」。sequence之中，依照由左到右的順序，挑幾個數字出來，就是subsequence。其中sub-的意思是「附屬、次要」。

例如1 3 5 2 9的其中一個子序列是3 9。

例如1 3 5 2 9的其中一個子序列是1 5 2 9。

空集合（不取）、原序列（全取），都是子序列！

Increasing

「遞增」。數字不斷增加。

例如3 9是遞增子序列。

例如1 5 2 9不是遞增子序列。

遞增的數學性質很強，可以設計高速演算法。

Longest Increasing Subsequence（LIS）

「最長遞增子序列」。所有子序列當中，遞增的、最長的子序列，可能有許多個。

例如1 3 5 2 9的LIS是1 3 5 9。

找出其中一個LIS，有快速的演算法，接下來將為各位介紹。

找出所有的LIS，以上述演算法作為基礎。

演算法

錯誤的做法：紀錄每種前綴的LIS。online演算法，一次讀取一個數字，窮舉先前每種前綴的LIS，看看哪一種接得最長。

正確的做法：紀錄每項數字為結尾的LIS。online演算法，一次讀取一個數字，窮舉先前每項數字為結尾的LIS，看看哪一種接得最長。

時間複雜度O(N²)，N是序列長度。

sequence           : -7 10  9  2  3  8  8  1

sequence           :(-7)10  9  2  3  8  8  1
LIS ends with s[0] : -7

sequence           : -7(10) 9  2  3  8  8  1
LIS ends with s[0] : -7
LIS ends with s[1] : -7 10

sequence           : -7 10 (9) 2  3  8  8  1
LIS ends with s[0] : -7
LIS ends with s[1] : -7 10
LIS ends with s[2] : -7     9

sequence           : -7 10  9 (2) 3  8  8  1
LIS ends with s[0] : -7
LIS ends with s[1] : -7 10
LIS ends with s[2] : -7     9
LIS ends with s[3] : -7        2

sequence           : -7 10  9  2 (3) 8  8  1
LIS ends with s[0] : -7
LIS ends with s[1] : -7 10
LIS ends with s[2] : -7     9
LIS ends with s[3] : -7        2
LIS ends with s[4] : -7        2  3

sequence           : -7 10  9  2  3 (8) 8  1
LIS ends with s[0] : -7
LIS ends with s[1] : -7 10
LIS ends with s[2] : -7     9
LIS ends with s[3] : -7        2
LIS ends with s[4] : -7        2  3
LIS ends with s[5] : -7        2  3  8

sequence           : -7 10  9  2  3  8 (8) 1
LIS ends with s[0] : -7
LIS ends with s[1] : -7 10
LIS ends with s[2] : -7     9
LIS ends with s[3] : -7        2
LIS ends with s[4] : -7        2  3
LIS ends with s[5] : -7        2  3  8
LIS ends with s[6] : -7        2  3     8

sequence           : -7 10  9  2  3  8  8 (1)
LIS ends with s[0] : -7
LIS ends with s[1] : -7 10
LIS ends with s[2] : -7     9
LIS ends with s[3] : -7        2
LIS ends with s[4] : -7        2  3
LIS ends with s[5] : -7        2  3  8
LIS ends with s[6] : -7        2  3     8
LIS ends with s[7] : -7                    1

UVa 111 231 437 497 10131 10534

計算Longest Increasing Subsequence的長度

這裡提供兩支程式碼，效果一樣！第一支程式碼是看s[i]能接在哪些數字後面。第二支程式碼是看s[i]後面能接上哪些數字。

const int N = 100; int s[N]; // sequence int length[N]; // 第 x 格的值為 s[0...x] 的 LIS 長度 int LIS() { // 初始化。每一個數字本身就是長度為一的 LIS。 for (int i=0; i<N; i++) length[i] = 1; for (int i=0; i<N; i++) // 找出 s[i] 能接在哪些數字後面， // 若是可以接，長度就增加。 for (int j=0; j<i; j++) if (s[j] < s[i]) length[i] = max(length[i], length[j] + 1); // length[] 之中最大的值即為 LIS 的長度。 int l = 0; for (int i=0; i<N; i++) l = max(l, length[i]); return l; } const int N = 100; int s[N]; // sequence int length[N]; // 第 x 格的值為 s[0...x] 的 LIS 長度 int LIS() { // 初始化。每一個數字本身就是長度為一的 LIS。 for (int i=0; i<N; i++) length[i] = 1; for (int i=0; i<N; i++) // 找出 s[i] 後面能接上哪些數字， // 若是可以接，長度就增加。 for (int j=i+1; j<N; j++) if (s[i] < s[j]) length[j] = max(length[j], length[i] + 1); // length[] 之中最大的值即為 LIS 的長度。 int l = 0; for (int i=0; i<N; i++) l = max(l, length[i]); return l; }

找出一個Longest Increasing Subsequence

額外建立一條陣列，記錄銜接關係。

const int N = 100; int s[N]; int length[N]; int prev[N]; // prev[x] 記錄 s[x] 是接在哪個數字後面 int lis[N]; void LIS() { for (int i=0; i<N; i++) length[i] = 1; // -1 代表 s[i] 是開頭數字，沒有接在其他數字後面。 for (int i=0; i<N; i++) prev[i] = -1; for (int i=0; i<N; i++) for (int j=i+1; j<N; j++) if (s[i] < s[j]) if (length[i] + 1 > length[j]) { length[j] = length[i] + 1; // s[j] 接在 s[i] 後面 prev[j] = i; } int l = 0, pos = 0; for (int i=0; i<N; i++) if (length[i] > l) { l = length[i]; pos = i; } print_LIS(pos); } // 遞迴版本 void print_LIS(int i) { if (prev[i] != -1) print_LIS(prev[i]); cout << s[i]; } // 迴圈版本，LIS順序顛倒。 // 暫時儲存於其他陣列，之後再依序印出。 void print_LIS(int i) { int l = length[i]; // LIS長度 for (; i != -1; i = prev[i]) lis[--l] = s[i]; l = length[i][j]; for (int i=0; i<l; ++i) cout << lis[i]; }

找出所有的Longest Increasing Subsequence

Backtracking，窮舉銜接關係。LIS數量最多2ᴺ個。

const int N = 100; int s[N]; int length[N]; void LIS() { for (int i=0; i<N; i++) length[i] = 1; for (int i=0; i<N; i++) for (int j=i+1; j<N; j++) if (s[i] < s[j]) length[j] = max(length[j], length[i] + 1); int l = 0; for (int i=0; i<N; i++) if (length[i] > l) l = length[i]; for (int i=0; i<N; i++) if (length[i] == l) print_LIS(i); } // 遞迴版本 void print_LIS(int i) { if (i == -1) {cout << '\n'; return;} for (int j=0; j<i; ++j) if (s[j] < s[i]) if (length[j] + 1 == length[i]) { print_LIS(j); cout << s[i]; } }

找出字典順序最小的Longest Increasing Subsequence

項次的字典順序：改為紀錄每項數字為開頭的LIS。

數字的字典順序：長度平手時，選擇數字較小者。

演算法

遞增、最長，兩件事分開處理。先處理遞增，再處理最長。

二元搜尋樹，節點是每項數字，擴充資訊是每項數字為結尾的LIS長度、以及其最大值。online演算法，一次讀取一個數字，搜尋次小的數字，累計LIS長度最大值。

時間複雜度O(NlogN)，N是序列長度。

演算法

當數字種類很少，紀錄每種數字當作結尾的LIS長度。

時間複雜度O(NR)，R是數字種類。

sequence :  1  1  2  3  5  4
s1 :
s2 :
s3 :
s4 :
s5 :

sequence : (1) 1  2  3  5  4
s1 : 1
s2 :
s3 :
s4 :
s5 :
/* 1 自成一個子序列, 無法接在別人後面 */

sequence :  1 (1) 2  3  5  4
s1 : 1
s2 :
s3 :
s4 :
s5 :
/* 1 自成一個子序列, 無法接在別人後面 */

sequence :  1  1 (2) 3  5  4
s1 : 1
s2 : 1 2
s3 :
s4 :
s5 :
/* 2 自成一個子序列, 亦可接在 s1 後面 */
/* s2 = max(1, s1 + 1) */

sequence :  1  1  2 (3) 5  4
s1 : 1
s2 : 1 2
s3 : 1 2 3
s4 :
s5 :
/* 3 自成一個子序列, 亦可接在 s1 s2 後面 */
/* s3 = max(1, s1+1, s2+1) */

sequence :  1  1  2  3 (5) 4
s1 : 1
s2 : 1 2
s3 : 1 2 3
s4 :
s5 : 1 2 3 5
/* 5 自成一個子序列, 亦可接在 s1 ... s4 後面 */
/* s5 = max(1, s1+1, ..., s4+1) */

sequence : 1  1  2  3  5 (4)
s1 : 1
s2 : 1 2
s3 : 1 2 3
s4 : 1 2 3 4
s5 : 1 2 3 5
/* 4 自成一個子序列, 亦可接在 s1 s2 s3 後面 */
/* s4 = max(1, s1+1, s2+1, s3+1) */

const int N = 100; const int R = 10; int s[N]; int array[R]; int LIS() { for (int i=0; i<R; i++) array[i] = 0; // 初始化 for (int i=0; i<N; i++) { // 自成一個子序列 if (array[s[i]] == 0) array[s[i]] = 1; // 亦可接在別人後面 for (int j=0; j<s[i]; j++) array[s[i]] = max(array[s[i]] , array[j]+1); } // 最大值即為LIS的長度 int l = 0; for (int i=0; i<R; i++) l = max(l, array[i]); return l; }

UVa 10051

演算法

當LIS長度很短，紀錄每種LIS長度的結尾數字（的位置）。結尾數字越小越好，以便接得更長。

時間複雜度O(NL)，L是LIS長度。

const int N = 100; int s[N]; int array[N+1]; // 長度為 i 的 LIS ，結尾數字是 array[i] 。 int LIS() { for (int i=1; i<=N; ++i) array[i] = +1e9; array[0] = -1e9; int l = 0; // 目前LIS長度 for (int i=0; i<N; ++i) { // LIS增長了 if (array[l] < s[i]) l++; // 算至目前的LIS長度 for (int j=l; j>0; --j) // 反向掃描，精簡表格。 if (array[j-1] < s[i]) array[j] = min(array[j], s[i]); } return l; }

演算法

紀錄每個數字在LIS當中的位置。位置越後面越好，以便接得更長。以Binary Search加速。

時間複雜度O(NlogL)，N是序列長度，L是LIS長度。

首先找到每個數字在LIS當中的最合適位置position[]。

sequence : -7 10  9  2  3  8  8  1
temp LIS :
position :

sequence :(-7)10  9  2  3  8  8  1
temp LIS : -7
position :  1		// -7 在 LIS 的第一個位置

sequence : -7(10) 9  2  3  8  8  1
temp LIS : -7 10
position :  1  2	// 10 在 LIS 的第二個位置，以此類推。

sequence : -7 10 (9) 2  3  8  8  1
temp LIS : -7  9
position :  1  2  2
/* 9 成為 LIS 的潛力比 10 大, 所以以 9 代替 10 */

sequence : -7 10  9 (2) 3  8  8  1
temp LIS : -7  2
position :  1  2  2  2
/* 2 成為 LIS 的潛力比 9 大, 所以以 2 代替 9 */

sequence : -7 10  9  2 (3) 8  8  1
temp LIS : -7  2  3
position :  1  2  2  2  3

sequence : -7 10  9  2  3 (8) 8  1
temp LIS : -7  2  3  8
position :  1  2  2  2  3  4

sequence : -7 10  9  2  3  8 (8) 1
temp LIS : -7  2  3  8
position :  1  2  2  2  3  4  4
/* 8 成為 LIS 的潛力比 8 大, 所以以 8 代替 8 */

sequence : -7 10  9  2  3  8  8 (1)
temp LIS : -7  1  3  8
position :  1  2  2  2  3  4  4  2
/* 1 成為 LIS 的潛力比 2 大, 所以以 1 代替 2 */

接下來從position[]之中找到LIS。從尾端往回找，先找到的就是正確的。因為LIS長度為4，所以先找到position[]之中的4。

sequence : -7 10  9  2  3  8 (8) 1
position :  1  2  2  2  3  4 (4) 2
LIS      :  -  -  -  8
/* search 4th, 8 is fourth LIS element */

sequence : -7 10  9  2 (3) 8  8  1
position :  1  2  2  2 (3) 4  4  2
LIS      :  -  -  3  8
/* search 3rd, 3 is third LIS element */

sequence : -7 10  9 (2) 3  8  8  1
position :  1  2  2 (2) 3  4  4  2
LIS      :  -  2  3  8
/* search 2nd, 2 is second LIS element */

sequence :(-7)10  9  2  3  8  8  1
position : (1) 2  2  2  3  4  4  2
LIS      : -7  2  3  8
/* search 1st, -7 is first LIS element */

最後得到其中一個LIS為-7 2 3 8，是最後出現的LIS。

順帶一提，如果想要得到最先出現的LIS，將原本序列前後顛倒，做Longest Decreasing Subsequence。

int LIS(vector<int>& s) { // 不得不判斷的特例 if (s.size() == 0) return 0; // 先塞入一個數字，免得稍後 v.back() 出錯。 vector<int> v; v.push_back(s[0]); for (int i=1; i<s.size(); ++i) { int n = s[i]; if (n > v.back()) v.push_back(n); else *lower_bound(v.begin(), v.end(), n) = n; } return v.size(); }

UVa 481

非嚴格遞增

請先看看這個例子。

sequence : -7 10  9  2  3  8 (8) 1
temp LIS : -7  2  3  8
position :  1  2  2  2  3  4  4
/* 8 成為 LIS 的潛力比 8 大, 所以以 8 代替 8 */

這個時候就不能用8來代替8，而要用8去代替比8稍大的數字。如果找不到比8稍大的數字，則直接將數字加在後面。上面的例子修改過後，就變成這樣。

sequence : -7 10  9  2  3  8 (8) 1
temp LIS : -7  2  3  8  8
position :  1  2  2  2  3  4  5
/* 8 可以接在 8 後面 */

宏觀視角

這個演算法找出了所有的子序列，依照長度排列。

Greedy Method，隨時記錄優良的子序列，逐步更新子序列，越串越長，求出LIS。

sequence       5 2 9 4 8 3
===========================
read 5 |  1 |  5     		// 長度1　　　　　（以5結尾最長的）
---------------------------
read 2 |  2 |    2   		// 長度1　　　　　（以3結尾最長的）
---------------------------
read 9 |  3 |      9 		// 長度1
       |  4 |    2 9 		// 長度2，接第二串
       |  5 |  5   9 		// 長度2，接第一串（以9結尾最長的）
---------------------------
read 4 |  6 |        4		// 長度1
       |  7 |    2   4		// 長度2，接第二串（以4結尾最長的）
---------------------------
read 8 |  8 |          8	// 長度1
       |  9 |        4 8	// 長度2，接第六串
       | 10 |    2     8	// 長度2，接第二串
       | 11 |  5       8	// 長度2，接第一串
       | 12 |    2   4 8	// 長度3，接第七串（以8結尾最長的）
---------------------------
read 3 | 13 |            3	// 長度1
       | 14 |    2       3	// 長度2，接第二串（以3結尾最長的）

read 5 |  5
read 2 |  2
read 9 |  2 9
read 4 |  2 4	// 同時記錄了第4串和第7串
read 8 |  2 4 8
read 3 |  2 3 8	// 同時記錄了第12串和第14串

Box Stacking Problem

有一堆尚未封裝的紙箱，把紙箱一個一個套起來存放。然而每個紙箱都有不同的長寬高。如果一個紙箱的三邊長，皆小於另一個紙箱的三邊長，這個紙箱才放得進去。請問最多能套幾層？

UVa 103

延伸閱讀

這個問題等價於有向無環圖的最長路徑，請見「Single Source Shortest Paths in DAG: Topological Sort」。

N個點　　　　<---> N個箱子
一條有向邊　 <---> 箱子可以放入另一個箱子
有向無環圖　 <---> 兩兩箱子之間的放入關係
最長路徑　　 <---> 箱子疊越多越好

演算法

箱子實施字典排序，然後尋找LIS。時間複雜度O(NlogN)。

Box Stacking Problem

有一堆封裝完畢的紙箱，把紙箱一個一個疊起來存放。然而每個紙箱都有不同的長寬高。如果一個紙箱的底部兩邊長，超過下方紙箱的頂部兩邊長，這個紙箱就會凸出一塊，這是我們不樂見的。請問最多能疊多高？

演算法

這個問題可以利用LIS的概念來解決。時間複雜度O(NlogN)。

一種變形問題：紙箱可以任意面朝上。這個問題是NP-complete問題。

一種變形問題：每種尺寸的紙箱都有無限多個，紙箱可以任意面朝上，兩邊長不可完全密合。此時這個問題可以利用LIS解決。時間複雜度O(NlogN)。

Sloane's Box Stacking Problem

有一堆封裝完畢的紙箱，把紙箱一個一個疊起來存放。然而每個紙箱都有不同的重量、不同的抗壓力量。如果一個紙箱上方的總重量，超過這個紙箱的抗壓力量，這個紙箱就會被壓傷，這是我們不樂見的。請問最多能疊多少個紙箱？又有多少種避免壓傷紙箱的疊法？

UVa 10154

延伸閱讀

這個問題等價於單機排程的逾時工作盡量少，請見「Single Machine Scheduling: Moore–Hodgson Algorithm」。

N個工作要完成　　　　  <---> N個箱子要疊
工作的處理時間　　　　 <---> 箱子的內容物重量
工作的完工期限　　　　 <---> 箱子的抗壓力量＋箱子的內容物重量＝承重能力
如期完工的工作越多越好 <---> 箱子疊越多越好

演算法：由上往下疊，累計重量越少越好。

一、依照承重能力由小到大排序。
二、依序疊紙箱，由上往下疊，求出LIS。

在一種合理的疊法當中，任意兩個緊鄰的紙箱，如果上方紙箱的承重能力比下方紙箱還強，那麼交換這兩個紙箱，仍是一種合理的疊法。也就是說，一種合理的疊法，經由多次兩兩交換緊鄰紙箱，使得由上往下來看，紙箱的承重能力恰好是遞增的。也就是說，我們可以依照承重能力排序紙箱，再來求LIS。

由上往下疊紙箱，累計重量，越小越好，讓下方更容易疊放紙箱。

時間複雜度O(NlogN + NL)。

const int N = 100; struct Box {int weight, strength;} box[N]; int array[N+1]; // 依照承重能力排序 bool cmp(Box box1, Box box2) { return box1.strength + box1.weight < box2.strength + box2.weight; } int box_stacking() { sort(box, box+N, cmp); for (int i=1; i<=N; ++i) array[i] = 1e9; array[0] = 0; int l = 0; // 目前LIS長度 for (int i=0; i<N; ++i) { // LIS增長了 if (array[l] <= box[i].strength) l++; // 算至目前的LIS長度 for (int j=l; j>0; --j) // 反向掃描，精簡表格。 // 下方可以疊紙箱 if (array[j-1] <= box[i].strength) // 累計重量 array[j] = min( array[j], array[j-1] + box[i].weight ); } return l; }

演算法：由下往上疊，剩餘力量越多越好。

一、依照抗壓力量由大到小排序。
二、依序疊紙箱，由下往上疊，求出LIS。

這個方法與前一個方法剛好互補。

由下往上疊紙箱，統計剩餘抗壓力量，越大越好，讓上方更容易疊放紙箱。

時間複雜度O(NlogN + NL)。

const int N = 100; struct Box {int weight, strength;} box[N]; int array[N+1]; // 依照抗壓力量排序 bool cmp(Box box1, Box box2) { return box1.strength > box2.strength; } int box_stacking() { sort(box, box+N, cmp); for (int i=1; i<=N; ++i) array[i] = 0; array[0] = 1e9; int l = 0; // 目前LIS長度 for (int i=0; i<N; ++i) { // LIS增長了 if (array[l] >= box[i].weight) l++; // 算至目前的LIS長度 for (int j=l; j>0; --j) // 反向掃描，精簡表格。 // 上方可以疊紙箱 if (array[j-1] >= box[i].weight) // 統計剩餘抗壓力量 array[j] = max( array[j], min(array[j-1] - box[i].weight, box[i].strength) ); } return l; }