Leetcode 300 最长上升子序列

动态规划

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

动态规划+二分

class Solution {
    
    public int lengthOfLIS(int[] nums) {
    
        //nums的长度
       int n = nums.length;
       //动态规划数组 其中dp[i] 存放长度为i+1的递增子序列的末尾数的最小值
       int[] dp = new int[n];
       int left = 0;
       int right = 0;
       Arrays.fill(dp,10001);
       //初始化长度1的字符串 结尾最小值是nums[0]
       dp[0] = nums[0];
       for(int i = 1; i < n;i++){
    
          int l = left;
          int r = right;
          // 寻找小于nums[i] 的最大值
          while(l < r){
    
              int m = l + (r-l+1) / 2;
              if(dp[m] >= nums[i])
                   r = m-1;
              else
                 l = m;
          }
          if(dp[l] >= nums[i]){
    //不存在小于nums[i]的数
              dp[0] = Math.min(dp[0],nums[i]);
          }
          else{
    
              dp[l+1] = Math.min(dp[l+1],nums[i]);
              right = Math.max(right,l+1);
          }
       }
       return right+1;
    }
}