300.最长上升子序列

题目描述：

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
题解：

//方法1,使用的是动态规划的方法，
//每一个数往前遍历，找到比他小的数已经上升的序列再加1，然后找到其中的最大值。

public static int getLength(int[] nums){
        if(nums.length==0){return 0;}
        int res[] = new int[nums.length];
        int max = 1;
        for(int index = 0;index<nums.length;index++){
            res[index] =1;

            if(index > 0){
                for(int in = index-1;in>=0;in--){
                    if(nums[in]<nums[index]){
                        res[index] = Math.max(res[in]+1,res[index]);
                        max = Math.max(res[index],max);
                    }
                }
            }
        }
        return max;
    }

方法2：使用贪心法
  使用一个result列表表示最长子序列
  当对数组的某一个进行判断的时候，
    如果该数大于列表中的最大数，即立刻添加
     否则：把result列表中对应位置替换掉，替换的规则是（被替换的数大于数组的数，被替换的数小于该数）
  例如：{10,9,2,5,3,7,101,18,-1,-2};
  result = [10]----i=0;
  result = [9]----i=1;
  result = [2]----i=2;
  result = [2,5]----i=3;
  result = [2,3]----i=4;
  result = [2,3,7]----i=5;
  result = [2,3,7,101]----i=6;
  result = [2,3,7,18]----i=7;
  result = [-1,3,7,18]----i=8;(因为获取的是子序列的长度，所以可以使用该方法。)
  result = [-1,-2,7,18]----i=9;
  对于寻找result中上述第二种情况的数，使用二分法进行查找

//二分法
    public static int getPosition_bina(List<Integer> nums,int s){
        int left = 0;int right = nums.size()-1;
        int mid = (left+right)/2;
        while(left < right){
            mid = (left+right)/2;
            if(nums.get(mid) >= s && (mid == 0 ||  nums.get(mid-1) < s)){
                return mid;
            }else if(nums.get(mid) < s){
                left = mid;
            }else if(nums.get(mid-1)>=s){
                right = mid;
            }
        }
        return mid;
    }

public static  int getLength2(int[] nums){
        List<Integer> res = new ArrayList<>();
        for(int index = 0;index<nums.length;index++){
            if(index==0){
                res.add(nums[index]);
            }else{
                if(nums[index] > res.get(res.size()-1)){
                    res.add(nums[index]);
                }else{
                    int po = getPosition_bina(res,nums[index]);
                    res.set(po,nums[index]);
                }
            }

        }
        return res.size();
    }