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;