Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.

• Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

nlogn

一种优化时间复杂度到O(nlgn)的解法，这里用到了二分查找法，所以才能加快运行时间哇。思路是，我们先建立一个数组ends，把首元素放进去，然后比较之后的元素，如果遍历到的新元素比ends数组中的首元素小的话，替换首元素为此新元素，如果遍历到的新元素比ends数组中的末尾元素还大的话，将此新元素添加到ends数组末尾(注意不覆盖原末尾元素)。如果遍历到的新元素比ends数组首元素大，比尾元素小时，此时用二分查找法找到第一个不小于此新元素的位置，覆盖掉位置的原来的数字，以此类推直至遍历完整个nums数组，此时ends数组的长度就是我们要求的LIS的长度，特别注意的是ends数组的值可能不是一个真实的LIS，比如若输入数组nums为{4, 2， 4， 5， 3， 7}，那么算完后的ends数组为{2， 3， 5， 7}，可以发现它不是一个原数组的LIS，只是长度相等而已，千万要注意这点。参见代码如下：

二分查找：找到第一个比target大的，返回他的index，在这里 当nums[mid] <target 时，让start = mid，所以，最后nums[start]的位置不会比target大，最后返回end；

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length == 0)
            return 0;
        
        List<Integer> list = new ArrayList<>();
        
        list.add(nums[0]);
        for(int i = 1; i < nums.length;i++){
            if(list.get(0) >= nums[i]){
                list.set(0,nums[i]);
            }
            
            else if(list.get(list.size()-1) <= nums[i]){
                list.add(nums[i]);
            }
            
            else{
                list.set(binarySearch(list,nums[i]),nums[i]);
            }
        }
        
        return list.size();
    }
    
    public int binarySearch(List<Integer> list, int target){
        int start = 0, end = list.size() -1;
        
        while(start + 1 < end){
            int mid = start + (end - start) / 2;
            
            if(list.get(mid) >= target){
                end = mid;
            }else{
                start = mid;
            }
        }
        
        return end;
    }
}