Longest Increasing Subsequence

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Have you met this question in a real interview?  
Clarification
What's the definition of longest increasing subsequence?

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

https://en.wikipedia.org/wiki/Longest_increasing_subsequence

Example
For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3
For [4, 2, 4, 5, 3, 7], the LIS is [2, 4, 5, 7], return 4

Challenge
Time complexity O(n^2) or O(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，只是长度相等而已，千万要注意这点。
    */

    //first element in mid array was MIN_VALUE.otherwise, need to change binary search methord
  public class Solution {
    /**
     * @param nums: An integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    public int longestIncreasingSubsequence(int[] nums) {
    //     // write your code here
        if (nums == null || nums.length == 0) {
    		return 0;
    	}

    	int[] end = new int[nums.length +1];
    	end[0] = Integer.MIN_VALUE;
    	for (int i = 1 ; i < end.length ;++i ) {
    		end[i] = Integer.MAX_VALUE;
    	}
    
        
    	for (int i = 0; i < nums.length ;++i ) {
    		int  p = binarySearch(end,nums[i]);
    		end[p] = nums[i];
    	}
    	
    	
    	int res = 0;
    	
    // 	for (int i = 0; i < end.length; i++ ) {
    // 		System.out.println(end[i]);
    		
    // 		if (end[i] != Integer.MAX_VALUE) {
    // 			res++;
    // 		}
    // 	}
    
        for(int i = nums.length ; i >= 1; i--){
            if (end[i] != Integer.MAX_VALUE) {
    			return i;
    		}
        }

    	return 0;
    
        //  int[] minLast = new int[nums.length + 1];
        // minLast[0] = Integer.MIN_VALUE;
        // for (int i = 1; i <= nums.length; i++) {
        //     minLast[i] = Integer.MAX_VALUE;
        // }
        
        // for (int i = 0; i < nums.length; i++) {
        //     // find the first number in minLast >= nums[i]
        //     int index = binarySearch(minLast, nums[i]);
        //     minLast[index] = nums[i];
        // }
        
        // for (int i = nums.length; i >= 1; i--) {
        //     if (minLast[i] != Integer.MAX_VALUE) {
        //         return i;
        //     }
        // }
        
        // return 0;
    }
    
     public int binarySearch(int[] nums, int target){
    	int start  = 0, end = nums.length -1;

    	while(start + 1 < end){
    		int mid = start + (end - start)/2;

    		if (nums[mid] < target) {
    			start = mid;
    		}
    		else{
    			end = mid;
    		}
    	}

    	return end ;
    }

}