Longest Increasing Subsequence

Longest Increasing Subsequence(LIS)

中文可以譯做「最長遞增子序列」。先來介紹subsequence這個字吧!subsequence是sub + sequence,sub有著「次要」的意思,而sequence是指數學之中的「數列」、「序列」。

1 3 5 2 9

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

3 9

例如3 9就是1 3 5 2 9的其中一個subsequence。

1 5 2 9

例如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的問題,主要有兩種演算法,一種是O(N^2)的,一種是O(NlogN)。先講簡單易懂的O(N^2)吧!

Longest Increasing Subsequence: Dynamic Programming

Recurrence

length(n) =  max  { length(i) + 1 : if s[i] < s[n] }
           0≤i≤n-1

n:第0項到第n項的LIS。
length(n):第0項到第n項的LIS長度。
s[n]:第n項數值。

計算Longest Increasing Subsequence的長度

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

找出一個Longest Increasing Subsequence

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

UVa 103 111 231 437 497 10131 10534

Longest Increasing Subsequence: Robinson-Schensted-Knuth Algorithm

演算法

採取Greedy策略,以Binary Search加速,達到O(NlogL),N是給定序列的長度,L是LIS的長度。

計算Longest Increasing Subsequence的長度

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

找出一個Longest Increasing Subsequence

很多演算法的書上都只說到如何去計算出LIS的長度,而沒有說要怎麼列出LIS。這裡介紹列出LIS的方法。

首先找到每個數字在LIS當中的合適位置position[],接下來就可以從position[]裡面找到真正的LIS。從尾巴開始往回找,先找到的就是正確的。因為LIS長度為4,所以就先找位置為4的。

最後得到LIS為-7 2 3 8。

LIS可能不止一個。上述方法會得到最後出現的LIS。若是要得到最先出現的LIS,該怎麼辦呢?最簡單的方式是:原本序列由右至左的做Longest Decreasing Subsequence就行了。

非嚴格遞增的Longest Increasing Subsequence

請先看看這個例子。

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

找出所有的Longest Increasing Subsequence

如果題目修改成:請列出所有的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: Dynamic Programming

演算法

還有一種特別的方法可以找出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

Longest Increasing Subsequence: Dynamic Programming

Recurrence

這裡我們要講解的是一種特別的LIS演算法,是把LIS的長度設計於狀態當中,作為狀態的其中一個維度,狀態本身儲存LIS的結尾數字。

根據Robinson-Schensted-Knuth Algorithm,我們知道當下的LIS的結尾數字越小越好,如此就更有潛力將LIS接得更長。此處的方法即是運用了Robinson-Schensted-Knuth Algorithm的概念。

f(n, l) =  min( f(n-1, l), s[n] : if f(n-1, l-1) < s[n] )

f(n, l):第0項到第n項,長度為l的遞增子序列,最小的結尾數值。
s[n]:第n項數值。

也可以改用索引值來記錄。這是比較適當的方式,只不過初始化會稍微麻煩一點。

f(n, l) =  min( f(n-1, l), n : if s[f(n-1, l-1)] < s[n] )

f(n, l):第0項到第n項,長度為l的遞增子序列,最小的結尾數值的索引值。
s[n]:第n項數值。

計算順序是依序讀取序列數值,然後每個數值都嘗試能不能接得更長。

時間複雜度為O(NL),N為數列長度,L為LIS的長度。

計算LIS的長度

可以精簡記憶體空間,手法就如同0/1 Knapsack Problem的做法。

沒有必要計算超出LIS長度的狀態。

Non-Squashing Stack of Boxes

【註:這個問題還沒有正式名稱。】

有一堆封裝完畢的紙箱,內容物的重量皆不同。現在要把紙箱一個一個疊起來存放,然而每個紙箱都有不同的抗壓力量,如果一個紙箱上方的總重量,超過這個紙箱的抗壓力量,這個紙箱就會被壓傷,這是我們不樂見的。請問一次最多能疊多少個紙箱?又有多少種不會壓壞紙箱的疊法呢?

【註:我有找到一個接近的問題,叫做Sloane's Box Stacking Problem,提供各位參考。】

UVa 10154

延伸閱讀

這個問題可以等價轉換成單機排程問題,可參考「Single Machine Scheduling, Minimize the Number of Tardy Jobs」。

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

第一種分割問題的方法:由上往下疊,累計重量越少越好。

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

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

由上往下疊紙箱的過程當中,需要不斷的累計紙箱的總重量,如果發現一個更好的疊法,就要更新總重量,並且讓總重量越小越好,如此一來下方就可以更容易添上紙箱。添上紙箱的條件,是該紙箱能夠承受上方全部紙箱的總重量,才能添上紙箱。

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

第二種分割問題的方法:由下往上疊,剩餘力量越多越好。

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

這個方法與前一個方法剛好互補。前面是以紙箱總重量的角度來思考,這裡則是以紙箱剩餘的抗壓力量來思考。

由上往下疊紙箱的過程當中,需要不斷的更新紙箱的抗壓力量,如果發現一個更好的疊法,就要更新抗壓力量,並且讓抗壓力量越大越好,如此一來上方就可以更容易添上紙箱。添上紙箱的條件,是該下方紙箱都能夠承受該紙箱的重量,才能添上紙箱。

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

不會壓壞紙箱的疊法共有幾種

【待補文字】