一、题目

假设存在一个序列d[0..8] = 2 1 5 3 6 4 8 9 7，计算最长递增子序列Longest Increasing Subsequence的长度。

二、解题思路

Notzuonotdied的解题思路

从d[0..8] = 2 1 5 3 6 4 8 9 7序列中，我们很容易看出最长递增子序列为[2, 3, 4, 8, 9]，长度为5。
算法实现过程：
- 创建一个子数组sub[n + 1]，长度为n + 1（数组的0位下标不使用），用于保存递增子序列。
- 注意：下面得出的答案{1, 3, 4, 7, 9}不是LIS，它只是存储的对应长度LIS的最小末尾。主要是要将思路转换为递增数组的替换。
- d[0] = 2，sub[1] = d[0] = 2，当前只有一个元素，len = 1，sub -> {2}
- d[1] = 1，sub[1] = 2，d[1] < sub[1]，所以覆盖原来的sub[1]，sub[1] = 1，len = 1，sub -> {1}
- d[2] = 5，sub[1] = 2，d[2] > sub[1]，所以sub[2] = d[2]，len = 2，sub -> {1, 5}
- d[3] = 3，sub[2] = 5，d[3] < sub[2]，所以覆盖原来的sub[2]，sub[2] = 3，len = 2，sub -> {1, 3}
- d[4] = 6，sub[2] = 3，d[4] > sub[2]，所以sub[3] = d[4]，len = 3，sub -> {1, 3, 4}
- d[5] = 4，sub[3] = 6，d[5] < sub[3]，所以覆盖原来的sub[3]，sub[3] = 4，len = 3，sub -> {1, 3, 4}
- d[6] = 8，sub[3] = 4，d[6] > sub[3]，所以sub[4] = d[6]，len = 4，sub -> {1, 3, 4, 8}
- d[7] = 9，sub[4] = 8，d[7] > sub[4]，所以sub[5] = d[7]，len = 5，sub -> {1, 3, 4, 8, 9}
- 下面到了一种特殊的情况了，请注意看：
- d[8] = 7，sub[5] = 9，d[8] < sub[5],所以覆盖原来的sub[4]，sub[4] = 7，len = 5，sub -> {1, 3, 4, 7, 9}
从上面的思路可以看出，这种算法其实就是递增数组的替换工程，所以可以采用二分查找的方式快速找出填坑的位置。
参考地址：最长递增子序列 O(NlogN)算法

Kotlin实现

fun main(args: Array<String>) {
    // 测试
    LIS(intArrayOf(2, 1, 5, 3, 6, 4, 8, 9, 7))
    LIS(intArrayOf(8, 6, 15, 14, 20, 21))
    LIS(intArrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10))
    LIS(intArrayOf(2))
    // 输入为空
    // TODO Kotlin默认不为空，不需要判断
}

/**
 * 在非递减序列 arr[start. .end]（闭区间）上二分查找第一个大于等于key的位置，
 * 如果都小于key，就返回e+1
 *
 * @param array 待查询的数组
 * @param start 开始位置
 * @param end 结束位置
 * @param key 查询的key值
 * */
fun upperBound(array: IntArray, start: Int, end: Int, key: Int): Int {
    var mid: Int
    var s = start
    var e = end
    // 如果最后一个小于key，直接返回e + 1
    if (array[e] <= key) return e + 1
    while (s < e) {
        mid = s + (e - s) / 2
        if (array[mid] <= key) s = mid + 1
        else e = mid
    }
    return s
}

/**
 * 最长递增子序列Longest Increasing Subsequence——O(NlogN)算法
 *
 * @param array 待查询的数组
 * @return 返回最长递增子序列的长度
 * */
fun LIS(array: IntArray): Int {
    var len = 1
    // 因为索引是从1开始的，所以大小需要加1
    val sub = IntArray(array.size + 1)

    sub[1] = array[0] // 初始化：长度为1的LIS末尾为d[0]
    for (i in 1..(array.size - 1)) {
        // 找到合适的插入位置
        val pos = upperBound(sub, 1, len, array[i])
        if (pos < 1) continue
        sub[pos] = array[i]
        if (len < pos) len = pos // 按需要更新LIS长度
    }

    println("最长递增子序列->${sub.toList()}，长度为->$len")
    return len
}

输出结果

最长递增子序列->[0, 1, 3, 4, 7, 9, 0, 0, 0, 0]，长度为->5
最长递增子序列->[0, 6, 14, 20, 21, 0, 0]，长度为->4
最长递增子序列->[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，长度为->10
最长递增子序列->[0, 2]，长度为->1