题解 | #最长递增子序列#

eachMaxSequenceLength 即上面的 dp 数组，表示以第 i 个元素结尾的最长递增子序列的长度

maxSequence 表示遍历数组时候存储的”伪最长递增子序列“，后面会解释为什么说是”伪“

首先对上面两个变量进行初始化，即将数组的第一个元素塞进 maxSequence ，对应的 eachMaxSequenceLength [0] = 1

然后对数组进行遍历，规则如下：

• 如果正在遍历的元素比 maxSequence 最后一个元素大，代表找到了更长的递增子序列，所以将当前元素赛进 maxSequence 末尾，eachMaxSequenceLength [i] 的值同步为 maxSequence 的长度
• 如果正在遍历的元素比 maxSequence 最后一个元素小，表明当前元素对于原有最长递增子序列（也就是现在的 maxSequence）再增长不会有贡献，但是它可能会为后面新的最长递增子序列做贡献，所以要将当前元素赛进 maxSequence ，规则是从 maxSequence 最左开始找到第一个不小于当前元素的位置（由于maxSequence 是有序的，所以这里可以用二分法），用当前元素替换掉它，当前元素在 maxSequence 的索引位置也就是以当前元素结尾最长递增子序列的长度

就这两个规则，一直遍历结束，也就得到了 eachMaxSequenceLength，利用该数组即可得到最长递增子序列。

根据前面的遍历规则，我们理解为什么说 maxSequence 是”伪“最长递增子序列了，因为按照第二个规则，在最长递增子序列右侧的元素都会被替换到它的左侧，那显然替换后的 maxSequence 都没按照数组元素原顺序排列，所以说 maxSequence 是”伪“的，但是 maxSequence 却发挥了它的作用：指导求 eachMaxSequenceLength

对于 [1,2,8,6,7,8,9]，假设按我们的步骤走到了如下状态：

maxSequence = [1, 2, 8]
eachMaxSequenceLength = [1, 2, 3]

当前遍历到了第四个元素：6，这个时候 maxSequence 还没变“伪”，至少目前它还是纯正的最长递增子序列，现在想求以 6 结尾的最长递增子序列长度，我们可以直接看 maxSequence 有多少个小于 6 的数，因为 maxSequence 出现的数一定都是在 6 的左边，也就是满足序列顺序要求的，通过 maxSequence 很快可以求得以 6 结尾的最长递增子序列长度是 3。

这个时候 6 要怎么处理呢？不能丢掉，因为后面可能还有递增序列依赖这个 6，所以要想办法把它放进 maxSequence。让它替换了 2 的位置，也就变成了：

maxSequence = [1, 6, 8]
eachMaxSequenceLength = [1, 2, 3, 2]

按照我们的替换原则，我们可能有两点担心，担心过去和未来：

• 6 加入了 maxSequence，它就不再是“序列”了，不会影响后面继续求比 8 更大的序列吗？
• 6 加入了 maxSequence，后面如果有依赖 6 的递增序列怎么办？

仔细思考一下，这两个问题都不是问题！

首先，如果后续有比 8 大的数，我们仍然可以按照前面定的第一个规则得到最大递增子序列长度加 1。可能会有疑惑：1 6 8 在数组中不是序列，怎么还能这样算？别忘了，6 是替换了之前存在的元素的，虽然 1 6 8 序列是不对的，但是它们的长度是没问题的，所以说 maxSequence 是“伪”序列，但是也能其指导作用。

第二个担心，后续如果有依赖 6 的递增序列，比如是 7 ，它会按照一样的规则替换掉 8 ，我们会发现它和 6 的相对顺序是没有变化的，所以也不影响后续求新的递增序列长度！

综上，通过 maxSequence 这个“伪”最大递增子序列的构建规则，我们实现了 O(N*logN) 的时间复杂度，比动态规划快！

public int[] LIS(int[] arr) {
    if (arr == null || arr.length < 2) {
        return arr;
    }

    int n = arr.length;
    // eachMaxSequenceLength[i] 表示以第 i 个元素结尾的最长递增子序列的长度
    int[] eachMaxSequenceLength = new int[n];
    eachMaxSequenceLength[0] = 1;
    // maxSequence 表示使用贪心遍历时的最长递增子序列
    List<Integer> maxSequence = new ArrayList<>();
    maxSequence.add(arr[0]);
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxSequence.get(maxSequence.size() - 1)) {
            // 最长递增子序列长度可以再加 1
            maxSequence.add(arr[i]);
            eachMaxSequenceLength[i] = maxSequence.size();
        } else {
            // 在 maxSequence 中找到第一个不小于 arr[i] 的位置，并替换它
            int index = find(maxSequence, arr[i], 0, maxSequence.size()-1);
            maxSequence.set(index, arr[i]);
            eachMaxSequenceLength[i] = index + 1;
        }
    }
    // 根据 maxSequenceLength 和 eachMaxSequenceLength 来找到最长递增子数组
    int[] res = new int[maxSequence.size()];
    int index = maxSequence.size();
    for (int i = n - 1; index > 0; i--) {
        if (eachMaxSequenceLength[i] == index) {
            // 每个最大长度取 eachMaxSequenceLength 数组中最右侧的值，可以反证
            res[--index] = arr[i];
        }
    }
    return res;
}

// 在 [left, right] 范围内找到最左边不小于 traget 的位置
private int find(List<Integer> maxSequence, int target, int left, int right) {
    if (left == right) {
        return left;
    }

    int mid = left + (right - left) / 2;
    if (maxSequence.get(mid) == target) {
        return mid;
    } else if (maxSequence.get(mid) > target) {
        return find(maxSequence, target, left, mid);
    } else {
        return find(maxSequence, target, left + 1, right);
    }
}