最長(zhǎng)遞增子序列問題研究

喬明澤　宋傳鳴

摘? 要： 本文采用分治策略和動(dòng)態(tài)規(guī)劃策略探討了最長(zhǎng)遞增子序列問題的兩種解法，并分析了算法的計(jì)算復(fù)雜度。結(jié)果表明，本文算法的時(shí)間復(fù)雜度和空間復(fù)雜度分別為O（nlogn）和O（n）。

關(guān)鍵詞： 最長(zhǎng)遞增子序列;分治;動(dòng)態(tài)規(guī)劃;算法

中圖分類號(hào)： TP391? ? 文獻(xiàn)標(biāo)識(shí)碼： A? ? DOI：10.3969/j.issn.1003-6970.2019.07.005

本文著錄格式：?jiǎn)堂鳚?，宋傳鳴. 最長(zhǎng)遞增子序列問題研究[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? 引言

最長(zhǎng)遞增子序列（Longest Increasing Subsequence， LIS）問題是計(jì)算機(jī)算法學(xué)、隨機(jī)矩陣?yán)碚?、表示理論、組合數(shù)學(xué)和生物信息學(xué)領(lǐng)域的典型問題之一[1]，其問題描述如下：設(shè)L是一個(gè)有n個(gè)元素的序列 。若L存在某子序列? ? 滿足? ?，則稱l是L的一個(gè)遞增子序列，并稱m為遞增子序列l(wèi)的長(zhǎng)度。最長(zhǎng)遞增子序列問題就是要求序列L的一個(gè)長(zhǎng)度最長(zhǎng)的遞增子序列。

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

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

本文內(nèi)容安排如下：第1節(jié)討論最長(zhǎng)遞增子序列問題的分治解法;第2節(jié)首先證明最長(zhǎng)遞增子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，然后詳細(xì)論述其動(dòng)態(tài)規(guī)劃解法;第3節(jié)總結(jié)全文。

1? 最長(zhǎng)遞增子序列的分治解法

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

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

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

其次，以L1的最長(zhǎng)遞增子序列為基礎(chǔ)向L2序列擴(kuò)展，得到一個(gè)遞增子序列a。

再次，以L2的最長(zhǎng)遞增子序列為基礎(chǔ)向L1序列擴(kuò)展，得到一個(gè)遞增子序列b。

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

對(duì)于L1和L2的最長(zhǎng)遞增子序列求解，由于其形式與原問題完全相同，解法與L的最長(zhǎng)遞增子序列解法一致。故此，為了保證分治算法具有較低的時(shí)間復(fù)雜度，關(guān)鍵環(huán)節(jié)是如何高效地將L1和L2的解合并為L(zhǎng)的解。

1.2? 子問題解的合并

將原序列 劃分成兩個(gè)相互獨(dú)立的子序列， 、? ?，然后遞歸求得BL和BR的最長(zhǎng)遞增子序列bl和br，然后將bl和br擴(kuò)展為L(zhǎng)的最長(zhǎng)遞增子序列sub。

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

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）

//以左子數(shù)組的最長(zhǎng)遞增子序列為基礎(chǔ)，向右子數(shù)組擴(kuò)展，得到一個(gè)遞增子序列

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? ? ? //向右擴(kuò)展的區(qū)域[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

//以右子數(shù)組的最長(zhǎng)遞增子序列為基礎(chǔ)，向左子數(shù)組擴(kuò)展，得到一個(gè)遞增子序列

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? //向左擴(kuò)展的區(qū)域[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

//合并，數(shù)組sub即為求得的L的最長(zhǎng)遞增子序列

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問題的分治解法步驟

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

算法輸入：數(shù)組a，數(shù)組sub，起始下標(biāo)first和終止下標(biāo)last

算法輸出：最長(zhǎng)遞增子序列及其長(zhǎng)度

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

1：? ?if last-first=2 then? ? //遞歸結(jié)束的基準(zhǔn)條件

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? ?計(jì)算復(fù)雜度分析

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

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

2? 最長(zhǎng)遞增子序列的動(dòng)態(tài)規(guī)劃解法

動(dòng)態(tài)規(guī)劃是求解具有最優(yōu)子結(jié)構(gòu)性質(zhì)的最優(yōu)化問題的有效算法設(shè)計(jì)策略之一，其基本思想是將規(guī)模為n的問題分解成若干個(gè)子問題，這些子問題往往不是互相獨(dú)立的、而是重疊的，且滿足最優(yōu)子結(jié)構(gòu);每求解出一個(gè)子問題，就將其答案保存到數(shù)組中，從而避免重疊子問題的多次計(jì)算;最后以自底向上的方式從子問題的解得到原問題的解[5]。

2.1? 最長(zhǎng)遞增子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)

定理1 設(shè)序列L的最長(zhǎng)遞增子序列為? ? （1

證明? 假設(shè)b不是subL在 條件下的最長(zhǎng)遞增子序列，則存在另一個(gè)subL的遞增子序列? 1i，? ?，那么可以構(gòu)造 ，因?yàn)閖>i，所以l2子序列的長(zhǎng)度大于l1子序列的長(zhǎng)度，l2才是L的最長(zhǎng)遞增子序列。這與l1是L的最長(zhǎng)遞增子序列相矛盾。因此，假設(shè)不成立，即b是 subL在 條件下的最長(zhǎng)遞增子序列。證畢。

由上述定理可知，最長(zhǎng)遞增子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

2.2? 一般解法

依據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)，可以得到最長(zhǎng)遞增子序列問題的解的遞歸表達(dá)式為：

（1）

由此即可獲得下文的最長(zhǎng)遞增子序列問題的動(dòng)態(tài)規(guī)劃解法。

每個(gè)數(shù)據(jù)元素采用的數(shù)據(jù)結(jié)構(gòu)為：

struct node

{

DataType data; //結(jié)點(diǎn)的值

int pre; //結(jié)點(diǎn)的前序

unsigned int count; //以該結(jié)點(diǎn)為結(jié)尾的遞增子序列的長(zhǎng)度

};

算法輸入：保存在node a[M]數(shù)組中的n個(gè)元素

算法輸出：最長(zhǎng)遞增子序列及其長(zhǎng)度

算法LIS_DM1 （a）

0：? ? 初始化數(shù)組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對(duì)應(yīng)a[0，..，i-1]的下標(biāo);

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]結(jié)尾的最長(zhǎng)遞增子序列

19：? ? ?end if

20：? ?end for

2.3? 基于二分查找和鏈棧的動(dòng)態(tài)規(guī)劃解法

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

每個(gè)數(shù)據(jù)元素采用的數(shù)據(jù)結(jié)構(gòu)為：

struct Element

{

DataType d;? ? ?//結(jié)點(diǎn)的值

Element* pre;? ?//d的前續(xù)坐標(biāo)，即在上一層鏈表中某節(jié)點(diǎn)

Element* next;

};

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

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

算法輸入：保存在node a[M]數(shù)組中的n個(gè)元素

算法輸出：最長(zhǎng)遞增子序列及其長(zhǎng)度

算法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] 時(shí)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）;? //輸出最長(zhǎng)遞增子序列

2.4? 計(jì)算復(fù)雜度分析

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

改進(jìn)動(dòng)態(tài)規(guī)劃解法，相對(duì)于上述的一般解法而言，在內(nèi)層循環(huán)中采用二分查找法，這樣時(shí)間復(fù)雜度就從O（n2）降到O（nlogn）。但是需要多消耗些空間用于保存數(shù)據(jù)，LIS_DM2算法運(yùn)用棧和鏈表輔助存儲(chǔ)，棧中元素有序，所以能使用二分查找，提高效率。具體分析如下。

因?yàn)閟[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指向的鏈表中。

故其時(shí)間復(fù)雜度為T（n）=O（nlogn），空間復(fù)雜度為S（n）=O（n）。

3? 結(jié)束語

最長(zhǎng)遞增子序列問題是計(jì)算機(jī)算法設(shè)計(jì)與分析中的典型問題，在數(shù)學(xué)、物理等學(xué)科中亦有廣泛應(yīng)用。本文采用分治和動(dòng)態(tài)規(guī)劃策略設(shè)計(jì)了兩種最長(zhǎng)遞增子序列求解算法，并給出了詳細(xì)的實(shí)現(xiàn)步驟，其時(shí)間復(fù)雜度均為O（nlogn），空間復(fù)雜度為O（n）。

參考文獻(xiàn)

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

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

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

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

[5] 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M]. 第4版. 北京： 電子工業(yè)出版社， 2012.