300. Longest Increasing Subsequence

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

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that 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?

对于num[i]来说，以nums[i] 为结尾的最长sequence是找到i位置左边比nums[i]小，但是path最长的的数的结果+1

dp[i] = 1+ dp[j] where nums[j] < nums[i] and j < i

问题变成了如何找到这个j

显然O(n^2)可以解决。

如何O(nlgn)？

Binary Search 是在sorted基础上。
我们需要path长度有小到大。
因此可以用一个array，array的index就是长度。
除此以外，我们还需要知道这个长度的最小的最后一位的index。array[i]存的是长度为i的sequence的最后一位的最小可能num值。

   public int lengthOfLIS(int[] nums) {  
     int[] dp = new int[nums.length+1];   
     if(nums.length==0) return 0;  
     int len = 1;dp[1] = nums[0];  
     for(int i = 1; i < nums.length; i++){  
       //find the last smaller index  
       int idx = binarySearch(dp,1,len,nums[i]);  
       dp[idx] = nums[i];  
       len = Math.max(idx,len);  
     }  
     return len;  
   }  
   public int binarySearch(int[] dp,int lo,int hi, int n){  
     while(lo < hi){  
       int mid = lo + (hi-lo)/2;  
       if(dp[mid] >= n) hi = mid;  
       else lo = mid + 1;  
     }  
     if(dp[lo] < n) return lo+1;  
     return lo;  
   }