演算法知識 - Longest Increasing Subsequence 最長遞增子序列(時間複雜度 O(nlogn) 與 時間複雜度 O(n^2))

Longest Increasing Subsequence 介紹

以下簡稱 LIS，在一個陣列中找出最長遞增的序列，序列是甚麼？舉例：

• 1 3 4 2 5
  則此 LIS 的長度為 3，符合最長長度的有三種：

• 1,3,4
• 1,2,5
• 1,4,5

只要相對位置有達到遞增，且數值也有遞增則符合遞增序列的意思。

在一些數學研究會涉及此演算法，且此演算法有兩種不一樣的時間複雜度，一種為 \(O(N^2)\) 另一種則為 \(O(n /log n)\)

這裡我們則是介紹比較快的方法，\(O(n \log n) \)

Longest Increasing Subsequence 原理

二分搜尋 + 陣列 = LIS，這是最好的解釋了XD。

產生兩個陣列 t , d ， t 用來記錄當前最長序列，d 則用來記錄當前 LIS 有包括此數值的前一個數值位置。

針對不同的題型，必須使用不同的 LIS

• 時間複雜度 \(O(n log n\)，當每個數值權重相等時使用
• 時間複雜度 \(O(n log n\)，當每個數值權重不一定相等或相等都可以使用，但效率不好

QUESTION: 你在解釋甚麼，太爛了吧XD。

我也覺得，所以我們用舉例的。

假設我們要在 10 30 20 40 50 找出 LIS，那透過我們的原理要怎麼做呢？

Step1: 初始化 t , d 並 i = 1 , 放入 10

由於 t 是紀錄最長陣列，且我們一定能夠保證 LIS 最長長度一定有 1，則是因為隨機在數列中拿出一個元素都可以是 LIS 長度為 1 而得證。

所以我們就在 t[1] 直接放入第一個數值的 index，這裡很重要，t and d 都是紀錄數值的 index。

由於 d[1] 是數列中的第一個 LIS 長度一定只有 1，所以設定成 0，表示他沒有前一個數值

t[1] = 1 ; 
d[1] = 0 ;

Step 2 : i = 2 , 放入 30

因為 30 有比 10 大，因此只需要在 LIS 增加長度即可，因此 LIS 的第二個長度放入數值的 index。

d[2] 則記錄當前最長的 LIS 此數值的前一個值，表示 d[2] 如果要往前回朔就是找此值。

t[2] = 2 ; 
d[2] = t[1]

Step 3 : i = 3 , 放入 20

由於 20 沒有比 30 大，於是我們必須要使用二分搜尋法，找出 2 在 t 這個陣列中適合放入哪個位置，由於二分搜尋的時間複雜度是 \(O(\log n)\)，因此再根據此陣列的長度 \(* n \)，就會符合此演算法的時間複雜度 \(O(n \log \ n)\)。

我們找到 t[2] = 3，所以我們把 t[2] 的值改成 2，為甚麼要這樣做呢？很簡單，因為如果 t[] 的數值越小代表之後可以放進去的數值會有可能比現在的數值還更多機會擴增 LIS，假如下一個是 25，那如果這邊沒有先將數值改成 20，25 就沒辦法擴增 LIS 了，因此才要做改值。

這裡為甚麼 d[3] = t[1] 呢？因為我們將 t[2] 放入當前的值，因此在現在的 t[1] 則是我們現在 d[3] 要記錄的前一個 LIS 數值，之後從 d[3] 不斷回推時可以發現只要回推 2 次就會回到 d[0]。

t[2] = 3 ;
d[3] = t[1] ;

Step 4: i = 4 , 放入 40

因為 40 有比 20 大，因此只需要在 LIS 增加長度即可，因此 LIS 的第三個長度放入數值的 index。

d[4] 則記錄當前最長的 LIS 此數值的前一個值，表示 d[4] 如果要往前回朔就是找此值。

t[3] = 4 ; 
d[4] = t[2] ;

Step 5: i = 5 , 放入 50

道理與 Step4 相同
因為 50 有比 40 大，因此只需要在 LIS 增加長度即可，因此 LIS 的第四個長度放入數值的 index。

d[5] 則記錄當前最長的 LIS 此數值的前一個值，表示 d[5] 如果要往前回朔就是找此值。

t[4] = 5 ;
d[5] = t[3] ;

Step 6: 完成了！此時我們簡單檢查一下，t 陣列裡的數值是不是最長 LIS

array	0	1	2	3	4	5
t	0	1	3	4	5	-
value	0	10	20	40	50	-

OK，沒錯，LIS 正確無誤。

OK, 現在問題被我們解決成是 Binary Search 了，那我們就來做吧！

關於 Binary Search 的部分就先去看大衞的筆記即可。

LIS 實作與說明，時間複雜度 \(O(n log n)\)

版本一 學習版

在程式碼進行說明，相信會比較好理解些。

#define N 
int b[N] , t[N] , d[N] , n ; 
// b 是原本的數列
// t 則是當前 LIS 的數列
// d 則是在 LIS 中此數值的前一個數值

int bs(int l , int r , int v){ //二分搜尋法
    int m ;
    while(r>l){
        m = (r+l) / 2 ;
        if(b[v] > b[t[m]] ) l = m+1 ;
        else r = m ;
    }
    return r ;
}

int lis(){
    int len = 1 , cur ; //LIS 最小長度為 1，因此 len = 1
    //cur 則是二分搜尋中找到的位置
    d[1] = 0 , t[1] = 1 ; //初始化 LIS 需要用到的兩個陣列
    for(int i = 2 ; i <= n ; i++){ //
        if(b[i] > b[t[len]] ){ //如果此數值比 LIS 中最長的數值還大時就直接增長
            d[i] = t[len] ; //d[i] 就則是在 LIS 中此數值的前一個數值
            t[++len] = i ; //增長 t 的長度
        } 
        else{ // 表示目前的數值可以替換此 LIS 中某個數值
            cur = bs(1,len,i);  // 二分搜尋找出此位置
            t[cur] = i ; //將原本 LIS 的 cur 值替換成 i 
            d[i] = t[cur-1] ; // 由於我們將 i 放入 t[cur]，所以我們的 d 就是找 t[cur-1]
        }
    }
    return len ; //回傳最長 LIS
}