最長遞增子序列問題研究

喬明澤　宋傳鳴

摘? 要： 本文采用分治策略和動態規劃策略探討了最長遞增子序列問題的兩種解法，并分析了算法的計算復雜度。結果表明，本文算法的時間復雜度和空間復雜度分別為O（nlogn）和O（n）。

關鍵詞： 最長遞增子序列;分治;動態規劃;算法

中圖分類號： TP391? ? 文獻標識碼： A? ? DOI：10.3969/j.issn.1003-6970.2019.07.005

本文著錄格式：喬明澤，宋傳鳴. 最長遞增子序列問題研究[J]. 軟件，2019，40（7）：3134

【Abstract】： By employing the divide-and-conquer and dynamic programming strategies， this paper discusses two algorithms of the longest increasing subsequence problem. The computational complexity of two algorithms was subsequently analyzed. The analysis results show that the time complexity and spatial complexity of two proposed algorithms achieve O（nlogn） and O（n）， respectively.

【Key words】： Longest increasing subsequence; Divide-and-conquer; Dynamic programming; Algorithm

0? 引言

最長遞增子序列（Longest Increasing Subsequence， LIS）問題是計算機算法學、隨機矩陣理論、表示理論、組合數學和生物信息學領域的典型問題之一[1]，其問題描述如下：設L是一個有n個元素的序列 。若L存在某子序列? ? 滿足? ?，則稱l是L的一個遞增子序列，并稱m為遞增子序列l的長度。最長遞增子序列問題就是要求序列L的一個長度最長的遞增子序列。

目前，最長遞增子序列問題已經被廣泛研究。文獻[2，3]分別給出了該問題的動態規劃解法;文獻[1]首先將LIS問題轉化為最長公共子序列問題，再利用動態規劃算法求解;文獻[4]則將LIS問題轉化為圖的最長路徑問題進行動態規劃求解。上述算法的計算時間復雜度均為O（n2）。在總結和分析現有算法不足之后，文獻[1]利用數組鏈表和二分查找改進了典型動態規劃算法中的查找操作，從而將算法的時間復雜度降低到O（nlogn），但是其輔助空間較大，且算法較為復雜。另外，國內尚鮮見關于最長遞增子序列問題的詳細實現過程且其時間復雜度達到O（nlogn）的研究資料。

本文利用分治策略和動態規劃策略[5]設計了兩種最長遞增子序列問題的O（nlogn）復雜度算法。分治解法的基本思路是將長度為n的序列分解為長度較短的子序列，再遞歸求解這些子序列的LIS，最后將各個子序列的解合并成原序列的解;動態規劃解法的基本思路與分治法類似，不同之處在于前者用一個數組來記錄那些已解決的子問題的答案，從而避免重復子問題的計算，降低時間復雜度。

本文內容安排如下：第1節討論最長遞增子序列問題的分治解法;第2節首先證明最長遞增子序列問題具有最優子結構性質，然后詳細論述其動態規劃解法;第3節總結全文。

1? 最長遞增子序列的分治解法

分治是一種簡單、直接的算法設計策略，其基本思想是將一個規模為n的問題分解為k個規模較小的、互相獨立的子問題且與原問題相同。遞歸計算每個子問題，然后將各個子問題的解合并為原問題的解[5]。依據此思想，下面討論本文的求解思路。

1.1? LIS問題分治解法的主要思路

首先，將序列L大致平均分成左、右兩個子序列L1和L2，遞歸求這兩個子序列的最長遞增子序列。

其次，以L1的最長遞增子序列為基礎向L2序列擴展，得到一個遞增子序列a。

再次，以L2的最長遞增子序列為基礎向L1序列擴展，得到一個遞增子序列b。

最后，序列L的最長遞增子序列即為a、b中的較長者。

對于L1和L2的最長遞增子序列求解，由于其形式與原問題完全相同，解法與L的最長遞增子序列解法一致。故此，為了保證分治算法具有較低的時間復雜度，關鍵環節是如何高效地將L1和L2的解合并為L的解。

1.2? 子問題解的合并

將原序列 劃分成兩個相互獨立的子序列， 、? ?，然后遞歸求得BL和BR的最長遞增子序列bl和br，然后將bl和br擴展為L的最長遞增子序列sub。

顯然，這里劃分的兩個子序列BL和BR沒有重疊部分，是相互獨立的，即具有子問題不重疊性質。對于子問題解的合并，給出下列合并思路。

1： bl←new int[（last-first）/2+1]

2： br←new int[（last-first）/2+1]

3： l ←LIS_DC（first，mid，bl）

4： r ←LIS_DC（mid，last，br）

//以左子數組的最長遞增子序列為基礎，向右子數組擴展，得到一個遞增子序列

5： for i←0 to l

6： sub[i]←bl[i]

7： end for

8： i←l-1 ，? p←i+1 ，? sub[p]←MAX

9：? for k←mid to last? ? ? //向右擴展的區域[mid，last）

10：? ? if sub[i]

11：? ? ++i ，? p←i+1 ，? sub[p]←a[k]

12：? ? else if sub[i]a[k] && sub[i]

13：? ? sub[p]←a[k]

14： else if sub[i]a[k] && sub[i]>a[k] && sub[i-1]

15：? ? sub[i]←a[k] ，? sub[p]←MAX

16：? end if

17：? end for

18：? if sub[p]=MAX then

19：? --p

//以右子數組的最長遞增子序列為基礎，向左子數組擴展，得到一個遞增子序列

20：? subr←new int[（last-first）/2+1]

21：? j←0，? subr[j]←br[0]，? q←j+1，? subr[q]←-MAX

22：? for k←mid-1 to first? //向左擴展的區域[first，mid）

23：? ? ?if subr[j]>subr[q] && subr[q]>a[k] then

24：? ? ++j ，? q←j+1 ，? subr[q]←a[k]

25：? ? ?else if subr[j]>subr[q]&&subr[q]a[k]

26：? ? ? ? ?subr[q]←a[k]

27：? ? ?end if

28：? end for

29：? if subr[q]= -MAX then

30：? --q

//合并，數組sub即為求得的L的最長遞增子序列

31：? if p+1>=q+r then

32：? s←p+1

33：? else s←q+r

34：? for k←q to 0

35： ? ? sub[i++]←subr[k]

36： for k←0 to r

37： ? ? sub[i++]←br[k]

1.3? LIS問題的分治解法步驟

根據上文的分析，下面給出本文提出的LIS問題的分治解法步驟。

算法輸入：數組a，數組sub，起始下標first和終止下標last

算法輸出：最長遞增子序列及其長度

算法LIS_DC （a，sub，first，last）

1：? ?if last-first=2 then? ? //遞歸結束的基準條件

2： ? if a[first]>a[first+1] then

3： ? ? ?sub[0]←a[first+1]，? return 1

4： ? else

5： ? ? ?sub[0]←a[first]，? sub[1]←a[first+1]，? return 2

6： end if

7： else if last-first=1 then

8： ? sub[0]←a[first]，? return 1

9： end if

10： mid←（first+last）/2

11： l←LIS_DC（first，mid，bl）

12： r←LIS_DC（mid，last，br）

1.4? ?計算復雜度分析

由于采用了二分法遞歸且遞歸函數中只存在一層循環，所以該算法的時間復雜度T（n）=O（nlogn）。

每次遞歸，當前函數都大致開辟i+2個sizeof（int）空間 ，所以總共大致開辟了2（n-1）+2logn個sizeof（int）空間，即空間復雜度S（n）=O（n）。

2? 最長遞增子序列的動態規劃解法

動態規劃是求解具有最優子結構性質的最優化問題的有效算法設計策略之一，其基本思想是將規模為n的問題分解成若干個子問題，這些子問題往往不是互相獨立的、而是重疊的，且滿足最優子結構;每求解出一個子問題，就將其答案保存到數組中，從而避免重疊子問題的多次計算;最后以自底向上的方式從子問題的解得到原問題的解[5]。

2.1? 最長遞增子序列問題具有最優子結構性質

定理1 設序列L的最長遞增子序列為? ? （1

證明? 假設b不是subL在 條件下的最長遞增子序列，則存在另一個subL的遞增子序列? 1i，? ?，那么可以構造 ，因為j>i，所以l2子序列的長度大于l1子序列的長度，l2才是L的最長遞增子序列。這與l1是L的最長遞增子序列相矛盾。因此，假設不成立，即b是 subL在 條件下的最長遞增子序列。證畢。

由上述定理可知，最長遞增子序列問題具有最優子結構性質。

2.2? 一般解法

依據最優子結構性質，可以得到最長遞增子序列問題的解的遞歸表達式為：

（1）

由此即可獲得下文的最長遞增子序列問題的動態規劃解法。

每個數據元素采用的數據結構為：

struct node

{

DataType data; //結點的值

int pre; //結點的前序

unsigned int count; //以該結點為結尾的遞增子序列的長度

};

算法輸入：保存在node a[M]數組中的n個元素

算法輸出：最長遞增子序列及其長度

算法LIS_DM1 （a）

0：? ? 初始化數組a，t←0

1：? ? for i←1 to n

2：? ? ? max←0

3：? ? ? for j←0 to i-1

4： ? ? ?if a[j].data

5： ? ? ? ? ?max←a[j].count， k←j? ?//max記錄著a[0，..，i-1]中count最大的值;

//k記錄著max對應a[0，..，i-1]的下標;

6： ? ? ?end if

7： ? ? end for

8： ? ? if max=0 then

9： ? ? ? goto 1

10：? ? ?end if

11：? ? ?a[i].count←max+1， a[i].pre←k

12：? ? ?if a[i].count>t then

13： ? t=a[i].count? ?//t記錄a[0，…，n-1]中count最大的值

14：? ? ?end if

15：? ?end for

16：? ?for i←0 to n

17：? ? ?if a[i].count=t then

18： ? output 以a[i]結尾的最長遞增子序列

19：? ? ?end if

20：? ?end for

2.3? 基于二分查找和鏈棧的動態規劃解法

由公式⑴和算法LIS_DM1可知，計算每個l（i）時都需要尋找滿足 條件的最大的l（j）。由于是l（j）無序的，順序查找需耗費O（n）的時間復雜度。若能利用特殊的數據結構實現有序的l（j），即可用二分查找方法完成最大l（j） 的搜索，從而將時間復雜度從O（n）降低到O（logn）。基于這種思路，本文設計了一種基于二分查找和鏈棧的動態規劃解法。

每個數據元素采用的數據結構為：

struct Element

{

DataType d;? ? ?//結點的值

Element* pre;? ?//d的前續坐標，即在上一層鏈表中某節點

Element* next;

};

Element? *s;? ? ? //s作棧

int Top=0;? //棧頂 棧中元素在s[0，Top）中

算法輸入：保存在node a[M]數組中的n個元素

算法輸出：最長遞增子序列及其長度

算法LIS_DM2（a）

0：? 初始化棧s，棧頂Top←0

1：? for i←0 to n-1

2：? ? s[i].q←NULL

3：? end for

4：? for i←0 to n-1

5：? ? l←0，mm←Top，h←Top，flag←false

6：? ? do while l<=h

7：? ? ? ?m←（l+h）/2

8：? ? ? ?if s[m].q=NULL then ? //s[m].q指向的鏈表無元素

9：? ? ? ? ? break

10：? ? ? end if

11：? ? ? if s[m].q→d>a[i] then? ? //s[m].qt→d是s[m].q鏈表中的最小元素

12：? ? ? ? mm←m，h←m-1? ? ? //mm保存著最近一次s[m].q→d>a[i] 時m的值

13：? ? ? else if s[m].q→d

14：? ? ? ? ?l←m+1

15：? ? ? else

16：? ? ? ? ?flag←true，break

17：? ? ? end if

18：? ?end do

19：? ?if flag=true

20：? ? ?goto Step 7

21：? ?end if

22：? ?將a[i]加入到s[mm].q指向的鏈表中

23：? end for

24：? rprint（s[Top-1].q）;? //輸出最長遞增子序列

2.4? 計算復雜度分析

一般解法中，LIS_DM1算法的計算量主要集中在二重循環階段，其時間復雜度為T（n）=O（n2）;另外，上述算法采用了1個包含n個元素的一維數組，故其空間復雜度為S（n）=O（n）。

改進動態規劃解法，相對于上述的一般解法而言，在內層循環中采用二分查找法，這樣時間復雜度就從O（n2）降到O（nlogn）。但是需要多消耗些空間用于保存數據，LIS_DM2算法運用棧和鏈表輔助存儲，棧中元素有序，所以能使用二分查找，提高效率。具體分析如下。

因為s[0].q→d，s[1].q→d，s[2].q→d，s[3].q→d，...，s[Top-2].q→d，s[Top-1].q→d是遞增有序的，所以可以采用二分查找法查找mm，使得s[0].q→d，s[1].q→d，s[2].q→d，s[3].q→d，...，s[mm-2].q→d，s[mm-1].q→d都小于a[i]，而從s[mm].q→d開始到s[Top-1].q→d都大于a[i]。這樣a[i]用頭插法添加到s[mm].q指向的鏈表中。

故其時間復雜度為T（n）=O（nlogn），空間復雜度為S（n）=O（n）。

3? 結束語

最長遞增子序列問題是計算機算法設計與分析中的典型問題，在數學、物理等學科中亦有廣泛應用。本文采用分治和動態規劃策略設計了兩種最長遞增子序列求解算法，并給出了詳細的實現步驟，其時間復雜度均為O（nlogn），空間復雜度為O（n）。

參考文獻

[1] 嚴華云， 李剛， 張建宏. 生物信息挖掘中LIS算法研究[J].計算機應用研究， 2009， 26（1）： 62-63， 6.

[2] SKIENA Steven S. The algorithm design manual[M]. 第2版 北京：清華大學出版社， 2009.

[3] 《編程之美》小組. 編程之美——微軟技術面試心得[M]. 北京： 電子工業出版社， 2012： 194-198.

[4] DASGUPTA S.， PAPADIMITRIOU C.， VAZIRANI U..算法概論[M]. 錢楓， 鄒恒明， 譯. 北京： 機械工作出版社， 2012： 157-159.

[5] 王曉東.計算機算法設計與分析[M]. 第4版. 北京： 電子工業出版社， 2012.