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?

 

使用dp，时间复杂度为O(n²)

1 public int lengthOfLIS(int[] nums) {
   //dp my 2         if(null==nums||0==nums.length){ 3             return 0; 4         } 5         int max= 1; 6         int[] re = new int[nums.length];//存放当前位置的最大长度 7         re[0]=1; 8         for(int i=1;i
     
      =0;j--){11                 if(nums[j]
      
       
        max){17                 max =re[i];18             }19         }20         return max;21     }
       
      
     

 

利用二分，时间复杂度为O(nlogn)

public int lengthOfLIS(int[] nums) {
   //二分 mytip        if(null==nums||0==nums.length){            return 0;        }        List
     
       re = new ArrayList<>();//        re.add(nums[0]);        int index = 0;        for(int i=1;i
      
       re.get(re.size()-1)){
   //如果大于最后一个元素，直接插入                re.add(nums[i]);            }            else{                index = bs(0,re.size()-1,re,nums[i]);//二分找到第一个不大于nusm[i]的数的下标，然后替换为当前数                re.set(index,nums[i]);                            }        }        return re.size();//数组长度为最大值    }    private int bs(int left,int right,List
       
         list,int num){        while(left<=right){            if(left >= right){                return left;            }            else{                int mid = left + (right - left)/2;                if(list.get(mid)