【leetcode】300. Longest increasing subsequence (dynamic programming, dichotomy)

subject ：

300.  The longest increasing subsequence 
 Give you an array of integers  nums , Find the length of the longest strictly increasing subsequence .
 Subsequence   Is a sequence derived from an array , Delete （ Or do not delete ） Elements in an array without changing the order of the rest . for example ,[3,6,2,7]  It's an array  [0,3,1,6,2,2,7]  The subsequence .

 Example  1：

 Input ：nums = [10,9,2,5,3,7,101,18]
 Output ：4
 explain ： The longest increasing subsequence is  [2,3,7,101], So the length is  4 .
 Example  2：

 Input ：nums = [0,1,0,3,2,3]
 Output ：4
 Example  3：

 Input ：nums = [7,7,7,7,7,7,7]
 Output ：1
 
 Tips ：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104

Method 1 ： Dichotomy ：

class Solution {
    
    public int lengthOfLIS(int[] nums) {
    
        int res = 0;
        int len = nums.length;
        int[] dp = new int[len];
        for(int n : nums){
    
            int i = Arrays.binarySearch(dp,0,res,n);
            if(i < 0){
    
                i = -(i+1);
            }
            dp[i] = n;
            if(i == res){
    
                res++;
            }
        }
        return res;
    }
}

• Time complexity ：O(n log n)
• Spatial complexity ：O(n)

Method 2 ： Dynamic programming

Ideas ：

1. State definition ：

   dp[i] The value of represents nums With nums[i] The length of the longest subsequence at the end .

2. Transfer equation ： set up j∈[0,i), Consider each round to calculate the new dp[i] when , Traverse [0,i) List intervals , Make the following judgment ：

   ① When nums[i]>nums[j] when ： nums[i] It can be connected to nums[j] after （ This problem requires strict increment ）, In this case, the length of the longest ascending subsequence is dp[j] + 1;
   ② When nums[i] <= nums[j] when ： nums[i] Can't connect to nums[j] after , In this case, the ascending subsequence does not hold , skip .

• All of the above 1. situation Calculated under dp[j] + 1 The maximum of , Until i The length of the longest ascending subsequence of （ namely dp[i]）. The implementation method is traversal j when , Each round of execution dp[i] = max(dp[i], dp[j] + 1).
• Transfer equation ： dp[i] = max(dp[i], dp[j] + 1) for j in [0, i).

3. The initial state ：

   dp[i]dp[i] All elements are set to 1, The meaning is that each element can at least be a separate subsequence , At this time, the length is 1.

4. Return value ：

   return dpdp List maximum , The global longest ascending subsequence length can be obtained .

5. Complexity analysis ：
   Time complexity O(N^2)： Traversal calculation dp List needs O(N), Calculate each dp[i] Need to be O(N).
   Spatial complexity O(N) ： dp The list takes up extra space of linear size .

// Dynamic programming.
class Solution {
    
    public int lengthOfLIS(int[] nums) {
    
        int len = nums.length;
        if(len == 0) return 0;
        int res = 0;
        int[]dp = new int[len];
        //  Array with 1 fill 
        Arrays.fill(dp, 1);
        for(int i = 0; i < len;i++){
    
            for(int j = 0;j < i;j++) {
    
                if(nums[i] > nums[j]) dp[i] = Math.max(dp[i],(dp[j]+1));
            }
            //  Record each round of dp[i]
            res = Math.max(res,dp[i]);
        } 
        return res;
    }
}