贪心算法day2（最长递增子序列）

目录

1.最长递增子序列

方法一：动态规划 

方法二：贪心+二分查找

1.最长递增子序列

链接：. - 力扣（LeetCode）

方法一：动态规划 

思路：我们定义dp[i]为最长递增子序列，那么dp[j]就是在小于i范围内的最长子序列，最长子序列最少为1，所以dp数组初始化为1.代码实行步骤如下：

这种情况下时间复杂度为O(n*2) ，空间复杂度为 O(n)

具体实现如下：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        for(int i = 0; i < n; i++){
            dp[i] = 1;
        }
        int ret = 1;
        for(int i = 1; i < n ; i++){
          for(int j = 0; j < i ;j++){
               if(nums[j] < nums[i]){
                dp[i] = Math.max(dp[j] + 1,dp[i]);
                 ret = Math.max(ret,dp[i]);
               }
          }
        }
        return ret;
    }
}

方法二：贪心+二分查找

思路：我们用数组来举个例子

第二种情况：(ret.get(mid) > nums[i])

这种情况下时间复杂度为nlogN(二分查找的时间复杂度为logN），空间复杂度为O(n)

代码： 

 public static int lengthOfLIS(int[] nums){
        int n = nums.length;
        ArrayList<Integer> ret = new ArrayList<>();
        ret.add(nums[0]);
        for (int i = 0; i < n; i++) {

            if(nums[i] > ret.get(ret.size() - 1)){
                ret.add(nums[i]);
            }else{
                int left = 0,right = ret.size() - 1;
                while(left < right){
                    int mid = (left + right)/2;
                    if(ret.get(mid) < nums[i]){
                        left = mid + 1;
                    }else{
                        right = mid;
                    }
                }
                ret.set(left,nums[i]);
            }
        }
        return ret.size();
         }