最长递增子序列

在计算机科学中，最长递增子序列（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) 项中的恒定因子）而言，这是最佳选择。