Longest Increasing Subsequence:
Dynamic Programming

Longest Increasing Subsequence

Longest Increasing Subsequence(LIS),中文可以譯做「最長遞增子序列」。先來介紹subsequence這個字吧!subsequence是sub + sequence,sub這個字有「分支」、「次要」之類的意思,而sequence就是指數學中的「數列」、「序列」。

1 3 5 2 9

像這樣就是一個由五個數字組成的sequence。至於subsequence,是指從一個sequence之中,依照由左到右的順序,挑幾個數字出來,就是subsequence。

3 9

像這樣就是1 3 5 2 9的其中一個subsequence。再舉一個例子。

1 5 2 9

這樣也是1 3 5 2 9的其中一個subsequence。至於空集合、原來的sequence,也都是1 3 5 2 9的subsequence!

接下來介紹increasing這個字。increasing是指數學中的「嚴格遞增」,就是數字不斷增加。1 3 5 2 9就不是一個遞增的sequence──因為在2的地方,這個sequence是在減少而非增加。至於3 9才是一個遞增的sequence。

每一個sequence都有長度。1 3 5 2 9的長度就是五,因為它由五個數字組成;3 9的長度就是二,因為它由兩個數字組成。LIS是指一個sequence當中,它擁有最長的長度、且嚴格遞增的那些subsequence(不一定只有一個唷)。1 3 5 2 9的LIS是1 3 5 9這個subsequence。

通常LIS的問題,只會要我們求出sequence的其中一個LIS即可。

計算LIS的長度

要解決LIS的問題,有兩種演算法,一種是O(N^2)的,一種是O(NlogN)。先講簡單易懂的O(N^2)吧!

這裡提供兩支程式碼,效果一樣!你可以用紙筆來畫畫看,模擬程式執行的樣子,應該就能容易理解了。

或者

找出一個LIS

用一個陣列紀錄一個數字是接在哪個數字後面。

LIS的題目有很多,這裡只列幾題當作參考。

UVa 103 111 231 437 497 10131 10534

Longest Increasing Subsequence:
Robinson-Schensted-Knuth Algorithm

Robinson-Schensted-Knuth Algorithm

這個演算法採取Greedy策略,以Binary Search加速,達到O(NlogN)。

計算LIS的長度

很多演算法的書上都有提到此演算法,所以就不贅述了。用C++ STL寫成的程式碼短短的很可愛:

找出一個LIS(uva481)

很多演算法的書上都只說到如何去計算出LIS的長度,而沒有說要怎麼列出LIS。這裡以uva481這一題的規定為原則,來介紹列出LIS的辦法。

如果要列出LIS,就還要再開一個一維陣列,叫做pos好了(position之意)。這個pos[]用來記錄這個數字是位於LIS的第幾個位置。現在假定輸入是-7 10 9 2 3 8 8 1。

LIS就從pos[]裡面找吧。從尾巴開始往回找,先找到的就是正確的。因為LIS長度為4,所以就先找位置為4的。

所以得到LIS為-7 2 3 8。

非嚴格遞增的LIS

請先看看這個例子。

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

uva481的題目限制原本是這樣的:如果有不止一個最長的嚴格遞增子序列,請輸出在輸入中最後出現的。若是修改成:如果有不止一個最長的嚴格遞增子序列,請輸出在輸入中「最先」出現的。那要怎麼辦呢?最快的方法就是由右至左的做Longest Decreasing Subsequence。

找出所有的LIS

如果題目修改成:請列出所有的LIS。這樣的話,我也不知道怎麼解決了。可能要寫個遞迴找出所有答案吧?

演算法討論

宏觀來看,這個演算法找出了所有的increasing subsequence,並依照特定順序排列。然後按順序記下幾個優良的subsequence。

原數列        5 2 9 4 8 3
==============
讀入5 |  1 |  5 			// 長度1          (以5結尾最長的)
--------------
讀入2 |  2 |    2   		// 長度1          (以3結尾最長的)
--------------
讀入9 |  3 |      9 		// 長度1
    |  4 |    2 9 		// 長度2,接第二串
    |  5 |  5   9 		// 長度2,接第一串(以9結尾最長的)
--------------
讀入4 |  6 |        4		// 長度1
    |  7 |    2   4		// 長度2,接第二串(以4結尾最長的)
--------------
讀入8 |  8 |          8		// 長度1
    |  9 |        4 8		// 長度2,接第六串
    | 10 |    2     8		// 長度2,接第二串
    | 11 |  5       8		// 長度2,接第一串
    | 12 |    2   4 8		// 長度3,接第七串(以8結尾最長的)
--------------
讀入3 | 13 |            3	// 長度1
    | 14 |    2       3	// 長度2,接第二串(以3結尾最長的)
讀入5 |  5
讀入2 |  2
讀入9 |  2 9
讀入4 |  2 4	// 同時記錄了第4串和第7串
讀入8 |  2 4 8
讀入3 |  2 3 8	// 同時記錄了第12串和第14串

在這個排列順序當中,長的subsequence排在短的subsequence之後,越串越長。

每當讀入一個數字時,所有能串接的subsequence,先前一定都出現過了──陣列裡也隨時紀錄著先前出現過、比較優良的subsequence。因此,運用greedy,逐步地更新陣列資料,必可求出LIS。

UVa 481

Longest Increasing Subsequence之三

Longest Increasing Subsequence之三

還有一種特別的方法可以找出LIS。這個方法有一個限制,那就是給定的sequence的數字種類很少。

假設給定的sequence,有一百個數字,但是只有五種不同的數字。對sequence中某一個位置的數字來說,它只可能接在這五種數字的其中一種數字後面;而所有subsequence的最後一個數字,也只有這五種可能。

有了這些特性,可以發現一個greedy方法。一、因為只有五種不同的數字──用五個變數,分別紀錄以該種數字做結尾的subsequence目前最長的長度。二、由左到右去讀取sequence,每次讀進一個數字,就檢查這個數字能不能讓目前紀錄中的subsequence 接得更長。三、要接得更長,就檢查讀進來的數字能不能分別接在那五種subsequence的後面,可以變長就加一。四、做完了一百個步驟之後,在五個變數之中,挑出最大的那個,就是LIS的長度。

用個實例來說明。假設給定的sequence是1 1 2 3 4 5 4。這裡以ss1到ss5,來代表以1到5結尾的subseqeuence目前最長的長度。

程式碼。這裡將數字分為五種,並且利用函式來得到某一種數字的值、用值來知道數字屬於哪一種。

如果要印出LIS的話,那麼就要一個二維的陣列紀錄。【待補程式碼】

一般來說,使用O(NlogN)的演算法也會比這個方法好。但是有些特別的題目卻可以這麼做。

UVa 10051