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?

Solution: 

1. O(n^2) with DP.

The idea is pretty simple, we use a counter array to maintain the length of longest increasing subsequence starting from current index.

So for example,

For  [10, 9, 2, 5, 3, 7, 101, 18],

count[7] would be 1 because starting from nums[7] which is the last element, should have longest increasing subsequence of length 1(it self).

count[6] would be 1 as well.

count [5]: because 7<101 and 7<18, so count[5] = Math.max(count[6],count[7])+1 =2;

similarly count[4]=count[5]+1=3; count[3]=count[5]+1=3,count[2]=count[4]/count[3]+1=4; count[1]=count[6]/count[7]+1 =2; count[0]=count[6]/count[7]+1=2;

The global maximum will be 4.

 public int lengthOfLIS(int[] nums) {  
     if(nums==null || nums.length==0) return 0;  
     int l=nums.length;  
     int[] count=new int[l];  
     int res=1;  
     count[l-1]=1;  
     for(int i=l-2;i>=0;i--){  
       count[i]=1;  
       for(int j=i+1;j<l;j++){  
         if(nums[i]<nums[j])   
         {  
           count[i]=Math.max(count[i],count[j]+1);  
         }  
       }  
       res=Math.max(res,count[i]);  
     }  
     return res;   
   }  

Another more advanced solution:
Time complexity: O(nlg(n))
A good reference: http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
Read it before you read my solution. My solution is little better than the reference.
Since we only need to know the length while we don't care the sequence itself, the case 1 and case 3 essentially are the same: find the insertion place and replace it.

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