LeetCode:300 最长递增子序列 -动态规划、贪心算法＋二分查找

• 1、动态规划解题思路
• 2、贪心算法+二分查找

1、动态规划解题思路

1. 首先设dp[i]的值是指以第i位为结尾的最长递增子序列长度。
2. 定义状态转移方程：dp[i] = max(dp[j])+1(0<=j<i)
3. 算法时间复杂度为O（N*N）

if(nums.length==0)
            return 0;
        //动态规划版本（无优化）
        int dp[] = new int[nums.length];
        //dp[i]是记录以nums[i]为结尾的最长公共子序列的长度
        //转换方程为：dp[i] = Math.max(dp[j])+1,j<i
        //初始化：全部初始化为1会怎么样？
        dp[0] = 1;
         int maxres = 1;
         for(int i = 0;i<nums.length;i++){
             int maxlen = 0;
             for(int j = 0;j<i;j++){
                 if(nums[j]<nums[i])
                     maxlen = Math.max(dp[j],maxlen);
             }
             maxlen = maxlen+1;
             maxres = Math.max(maxlen,maxres);
             dp[i] = maxlen;
         }
         return maxres;
        //此处结果不一定为dp[nums.length-1]！！
           

2、贪心算法+二分查找

1. 首先定义一个数组d[len]，里面存储的是长度为len的最小的nums[i]（nums是目标数组），（因为我们希望在子序列前面的数尽可能小（贪心原理），可以让子序列后面的数的上升空间尽可能的大）。
2. 然后遍历一遍nums数组，如果nums[i]小于当前的d[len]（也就是长度为len的数可以更小，使他等于nums[i]）可以进行二分查找查找在当前d数组中满足d[newlen-1]<nums[i]<d[newlen]的位置，将d[newlen]重新赋值为当前nums[i]。如果nums[i]大于当前d[len]则直接在d数组后面加上改nums[i]并使len加1.
3. 算法复杂度为O（nlogn）。

int erfen(int[] nums,int k,int g){
        int l = 0;
        int r = g;
        int mid = (l+r)/2;
        while(l<r){
            mid = (l+r)/2;
            if(nums[mid]<k)
                l = mid+1;
            else
                r = mid;
        }
        return l;
    }
//贪心算法+二分法查找
        int d[] = new int [nums.length+1];
        int len = 0;
        d[0] = nums[0];
        for(int i = 0;i<nums.length;i++){
            if(d[len]<nums[i]){
                len = len+1;
                d[len] = nums[i];
            }
            else if(d[len]>nums[i]){
                int t = erfen(d,nums[i],len);
                d[t] = nums[i];
            }
        }
        
        return len+1;