最长递增子序列LIS的O(nlogn)的求法

大家好，又见面了，我是你们的朋友全栈君。

最长递增子序列(Longest Increasing Subsequence)是指n个数的序列的最长单调递增子序列。比如，A = [1,3,6,7,9,4,10,5,6]的LIS是1 3 6 7 9 10。我们现在希望编程求出一个给定的数组，我们能得到LIS的长度。
关于LIS的求法使用DP算法的文章也很多，时间复杂度是O(n²)，这里，我们介绍一个只需要不到15行的Python代码或者Java代码来实现一个复杂度O(nlogn)的算法。

设tails是一个数组，用于存储在tails[i]中，所有长度为i+1的递增子序列的最小的尾元素。
例如，我们有一个nums = [4, 5, 6, 3]，那么所有的递增子序列是：

# 长度为1
[4], [5], [6], [3]          =>  tails[0] = 3
# 长度为2
[4, 5], [5, 6], [4, 6]      =>  tails[1] = 5
# 长度为3
[4, 5, 6]                   =>  tails[2] = 6

tails的第i个位置记录nums中长度为i+1的所有递增子序列中，结尾最小的数字。
我们很容易证明，tails是一个递增的数组。首先，tails[0]一定是所有元素中最小的那个数字min1，因为长度为1的子序列中，结尾最小的数字就是序列中最小的那个。同样，长度为2的子序列中，结尾最小的的那个子序列的结尾元素一定大于min1，因为首先所有长度为2的递增子序列，第二个元素一定比第一个元素大，如果长度为2的子序列中某个子序列的结尾元素小于min1，那么在第一次操作中，这个元素就会更新为min1。对于长度为3的子序列，假设之前tails已经存储了前两个结尾最小数[a, b]，若长度为三的子序列结尾数字c3小于b，即[c1, c2, c3]是一个递增子序列，且c3 < b，则必然有c2 < b，这样和之前的结论b是长度为2的递增子序列结尾最小元素矛盾。所以，通过这样的一步步的反证法，很容易证明tails一定是一个递增的数组。那么很容易通过二分查找， 找到在tails数组中需要被更新的那个数。
每次我们遍历数组nums，只需要做以下两步中的一步：

1. 如果 x 比所有的tails都大，说明x可以放在最长子序列的末尾形成一个新的自许下，那么就把他append一下，并且最长子序列长度增加1
2. 如果tails[i-1] < x <= tails[i]，说明x需要替换一下前面那个大于x的数字，以便保证tails是一个递增的序列，那么就更新tails[i]
   这样维护一个tails变量，最后的答案就是这个长度。

Python代码如下：

def lengthOfLIS(self, nums):
    tails = [0] * len(nums)
    size = 0
    for x in nums:
        i, j = 0, size
        while i != j:
            m = (i + j) // 2
            if tails[m] < x:
                i = m + 1
            else:
                j = m
        tails[i] = x
        size = max(i + 1, size)
    return size

举一个具体的例子来说，比如我们的目标数组是[3, 4, 7, 2, 5]。我们从前往后开始遍历数组。tails = [3, 0, 0, 0, 0]
1. x = 3，此时i = 0，直接令tails[0] = 3，tails = [3, 0, 0, 0, 0]。说明到目前为止长度为1的递增子序列末尾最小为3。
2. x = 4，此时i != j，但是x大于tails的末尾，直接另tail[1] = 4， tails = [3, 4, 0, 0, 0]。说明到目前为止长度为1的递增子序列末尾最小为3，长度为2的递增子序列末尾最小为4。
3. x = 7，大于tails的末尾，直接令tails[2] = 7，tails = [3, 4, 7, 0, 0]。说明到目前为止长度为1的递增子序列末尾最小为3，长度为2的递增子序列末尾最小为4，长度为3的递增子序列末尾最小为7.
4. x = 2，此时x小于tails的末尾，需要用二分查找到比x大的最小的那个数更新之，查找到tails中比2大的最小数是3，更新tail[0] = 2，此时tails = [2, 4, 7, 0, 0]。说明到目前为止长度为1的递增子序列末尾最小为2，长度为2的递增子序列末尾最小为4，长度为3的递增子序列末尾最小为7。这一步理解很关键，[2, 4, 7, 0, 0]的存在并不是说目前为止的递增子序列是2 4 7，而是长度分别为1，2， 3的递增子序列目前所能得到的最小结尾元素是2，4，7。我们这样做的目的就是，通过维护tails中的元素，保证每次对于长度为i+1的一个子序列对应的tails[i]元素最小，这样新元素的出现并替换前面的一个值，这就是在告诉我们，“虽然在我之前，你们形成了一个长度为m的递增序列，但是呢，你们长度为m这个序列的末尾最大的一个数比我还大，不如把我和末尾最大的那个元素换一下，这样你看咱们还是一个递增序列，长度也不变，但是我和你们更亲近”。别的元素一听是这么个道理啊，于是就踢出最后一个元素，换上了这个新的更小的元素。

在元素2还没进入的时候，形成的状态是这样的，我们从正面看就是我们得到那个tails数组，其实每个数组对应一个相应的递增序列，也就是从左侧或者右侧看得到的实际的递增序列。下面元素2进入：

因为2比3小，所以能够形成的长度为1的最小的递增子序列是2。其余不变。

1. x = 5， 通过比较，5比7小，比4大。

发生替换：

通过这个图我们也能很直观的看出来，此时的tails数组变成了[2, 4, 5, 0, 0]，而相应的长度为1，2，3的最小递增数组分别为[2], [3, 4], [3, 4, 5]。这样，如果再进入一个6，就直接放在5的后面，递增数组长度+1；反之，如果进来的是个1，就替换掉2。通过维护这样一个tails数组，我们就能够很方便的求出递增子序列的最大长度了。递增子序列的最大长度也就是当前tails数组中所能到达的最右侧的位置。
而这种方法通过二分查找，时间效率只有O(nlogn)，空间效率最坏情况也是O(n), 只需要维护一个长度为n的tails数组即可。
如果需要求的是非严格单调递增数组，只需要把if tails[m] < x:改为if tails[m] <= x:即可。

JAVA

public int lengthOfLIS(int[] nums) {
    int[] tails = new int[nums.length];
    int size = 0;
    for (int x : nums) {
        int i = 0, j = size;
        while (i != j) {
            int m = (i + j) / 2;
            if (tails[m] < x)
                i = m + 1;
            else
                j = m;
        }
        tails[i] = x;
        if (i == size) ++size;
    }
    return size;
}
// Runtime: 2 ms