[LeetCode] Longest Increasing Subsequence

参考：https://leetcode.com/discuss/71129/space-log-time-short-solution-without-additional-memory-java

思路：O(nlogn)
利用maximumLength来记录当前最大的子序列，并且在数组中从0到maximumLength-1存入这个子序列。
我们只关注这个子序列的最大值，也就是nums[maximumLength-1]，当前值和这个值的大小关系决定了目前的最大子序列能否继续扩大。如果能继续扩大，我们可以将当前值加入到这个子序列，否则需要将当前值插入到最大子序列里，为了是用未来可能存在的更大子序列来替换当前子序列。

例如：

[11, 15, 20, 12, 13]

从11开始到20， 我们可以得到当前最大子序列[11, 15, 20], maximumLength = 3，

12的时候，其小于20，当前最大子序列[11, 15, 20]不能扩展，但12可能是未来最大子序列里中的一个元素，我们可以将其和15替换，一方面11和12可以组成一个子序列（虽然不是最大），另一方面替换15对当前最大序列的扩展没有影响，毕竟我们只需要最大长度，而不是最大序列的每一个值。

判断完13的时候0到maximumLength-1的值为[11, 12, 13]，此时[11, 15, 20]和[11, 12, 13]均为最大子序列，但我们只关注结果。

假如给这个数组加一个值21，那么此时其跟13比较而不是20，但无论使用[11, 15, 20]还是[11, 12 ,13]对结果没有影响。假如给这个数组加一个值19，可以看到13使得其扩展。所以最大子序列的末尾越小越好，这也是为什么我们希望将小于当前最大子序列末尾的值插入替换到子序列里。

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int maximumLength = 1;
        for (int i = 1; i < nums.length; i++) {
            int previousIndex = 0;
            if (nums[i] > nums[maximumLength-1]) {
                nums[maximumLength++] = nums[i];
            }
            else if ((previousIndex = Arrays.binarySearch(nums, 0, maximumLength, nums[i])) < 0) {
                nums[-(previousIndex+1)] = nums[i];
            }
        }
        return maximumLength;
    }
}