Leetcode 300 longest ascending subsequence

Dynamic programming

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;
    }
}

Dynamic programming + Two points

class Solution {
    
    public int lengthOfLIS(int[] nums) {
    
        //nums The length of 
       int n = nums.length;
       // Dynamic programming array   among dp[i]  The storage length is i+1 The minimum value of the end number of the increasing subsequence of 
       int[] dp = new int[n];
       int left = 0;
       int right = 0;
       Arrays.fill(dp,10001);
       // Initialization length 1 String   The minimum value at the end is nums[0]
       dp[0] = nums[0];
       for(int i = 1; i < n;i++){
    
          int l = left;
          int r = right;
          //  Look for less than nums[i]  The maximum of 
          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]){
    // There is no less than nums[i] Number of numbers 
              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;
    }
}