最長遞增子序列

在計算機科學中，最長遞增子序列（longest increasing subsequence）問題是指，在一個給定的數值序列中，找到一個子序列，使得這個子序列元素的數值依次遞增，並且這個子序列的長度儘可能地大。最長遞增子序列中的元素在原序列中不一定是連續的。許多與數學、算法、隨機矩陣理論、表示論相關的研究都會涉及最長遞增子序列。解決最長遞增子序列問題的算法最低要求O(n log n)的時間複雜度，這裡n表示輸入序列的規模。

例子

對於以下的原始序列

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

最長遞增子序列為

0, 2, 6, 9, 11, 15.

值得注意的是原始序列的最長遞增子序列並不一定唯一，對於該原始序列，實際上還有以下三個最長遞增子序列

0, 4, 6, 9, 11, 15

0, 4, 6, 9, 13, 15

0, 2, 6, 9, 13, 15

相關算法

最長遞增子序列問題與最長公共子序列問題密切相關，後者具有動態規劃解決方案（時間複雜度為O(n ²)）：序列S的最長遞增子序列是S和T的最長公共子序列，其中T是對S進行排序的結果。但對於特殊情況，輸入是整數 1, 2, ..., n, 的排列，解決方案可以進一步改進，從而使時間複雜度降為O(n log n) 。

排列圖（permutation graph)中的最大團是由'定義該圖的排列中最長的遞減子序列'定義的, 求最長的遞減子序列在計算複雜度上（通過對所有數取它的負數）等同於求最長的遞增子序列。 因此，最長遞增子序列算法可用於有效地解決排列圖中的分團問題。

高效的算法

下面概述的算法使用數組和二分查找算法有效地解決了最長遞增子序列問題。 它依次處理序列元素，保存當前找到的最長的遞增子序列， 比如: [X[0]，X [1]]。在處理X[i]之後，算法會將值存儲在兩個數組中：

M[j] — 存儲值最小的X [k]的索引k，以使在範圍k≤i上，以X [k]結尾的長度為j的子序列增加。 注意：j ≤ (i+1)，因為j≥1表示遞增子序列的長度，而k≥0表示其終止的索引。

P[k] — 將X [k]的前任索引存儲在以X [k]結尾的最長遞增子序列中。

另外，該算法還存儲了一個變量L，該變量L表示到目前為止找到的最長的遞增子序列的長度。 下面的算法使用基於零的編號，為了清楚起見，M用M [0]填充，而M [0]未使用，因此M [j]對應於長度j的子序列。 實際的實現可以跳過M [0]並相應地調整索引。

請注意，在算法的任何時候，序列

X[M[1]], X[M[2]], ..., X[M[L]]

是遞增的。 因為，如果長度j≥2的子序列以X [M [j]]結尾，則長度j-1的子序列以較小的值結尾：即以X [P [M]結尾的子序列 [j]]。 因此，我們可以使用二分查找在O(log n)時間內完成搜索。

偽代碼如下：

A demo of the code.

P = array of length N
M = array of length N + 1

L = 0
for i in range 0 to N-1:
    // Binary search for the largest positive j ≤ L
    // such that X[M[j]] <= X[i]
    lo = 1
    hi = L
    while lo ≤ hi:
        mid = ceil((lo+hi)/2)
        if X[M[mid]] < X[i]:
            lo = mid+1
        else:
            hi = mid-1

    // After searching, lo is 1 greater than the
    // length of the longest prefix of X[i]
    newL = lo

    // The predecessor of X[i] is the last index of 
    // the subsequence of length newL-1
    P[i] = M[newL-1]
    M[newL] = i
    
    if newL > L:
        // If we found a subsequence longer than any we've
        // found yet, update L
        L = newL

// Reconstruct the longest increasing subsequence
S = array of length L
k = M[L]
for i in range L-1 to 0:
    S[i] = X[k]
    k = P[k]

return S

由於該算法對每個序列元素都執行二分查找，因此時間複雜度為O(n log n)。 弗雷德曼 Fredman (1975)討論了該算法的一種變體，他將其歸功於高德納。 在他研究的變體中，該算法在進行二分查找之前，測試每個值X [i]是否可以在常數時間內擴展當前最長的遞增序列。 通過這種修改，算法在最壞的情況下只會進行n log₂ n − n log₂log₂ n + O(n)個比較，對於比較算法（最高為O(n) 項中的恆定因子）而言，這是最佳選擇。