300 Longest increasing subsequence

https://leetcode.com/problems/longest-increasing-subsequence/

O(n^2)的方法很好想到，但是O(nlogn)的方法很难。有些题比如russian doll envelope不这样做会TLE，idea就是用dp[i]维护长度为i+1的LIS的最小ending值，这样才能为可能的增长留出空间，每次用binary search寻找能更新的位置。

注意Arrays.binarySearch的用法，以及它找不到target的时候的返回值是-smallest larger idx - 1

这也叫LIS 牌堆算法

class Solution {
    public int lengthOfLIS(int[] nums) {
        // dp[i]是长度为i+1的LIS的最小ending值
        // 注意dp本身并不一定是LIS
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int len = 1;
        for (int i = 1; i < nums.length; i++) {
            //找到num可以放在哪里
            //(可以用binary search，注意binary search要返回大于target的最小值，也就是insert idx)，
            //如果是在dp中间并且值较小就替换掉原来的值 这样能尽可能为以后的增长留出空间
            //如果在最后就扩大len，把它放在最后
            int num = nums[i];
            // [0, len)范围内搜索
            int idx = Arrays.binarySearch(dp, 0, len, num);
            // 如果没找到的话这个函数默认返回 -大于target最小值idx-1
            if (idx < 0) {
                idx = -(idx+1);
            }
            //替换掉大于它的最小值
            dp[idx] = num;
            // 如果是放最后了就增加len
            if (idx == len) {
                len++;
            }
        }
        return len;
    }
}