最长递增子序列

//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?
1.给出O(n2)的时间复杂度算法

 public int lengthOfLIS(int[] nums) {
            int dp[]=new int[nums.length];
            dp[0]=1;
            int max=1;
            for(int i=1;i<dp.length;i++){
                int maxValue=0;
                for(int j=0;j<i;j++){
                    if(nums[i]>nums[j]){
                        maxValue=Math.max(maxValue, dp[j]);

                    }
                }
                dp[i]=maxValue+1;
                max=Math.max(max, dp[i]);
                
            }
            return max;
        }

2.用二分查找给出O(nlogn)算法

image.png

 public int longestSequence(int[] a){
         int[] sub=new int[a.length];
         int length=0;
         for(int ele:a){
             int index=binarySearch(sub,ele,length);
             sub[index]=ele;
             if(index==length){
                 length++;
             }
                     
         }

         return length;
                 
     }
     
    private int binarySearch(int[] sub, int data, int length) {
        int l=0;
        int r=length;
        while(l<r){
            int mid=l+(r-l)/2;
            if(sub[mid]==data){
                return mid;
            }
            else if(sub[mid]>data){
                r=mid;
            }
            
            else{
                l=mid+1;
            }
        }
        return l;
    }