300. Longest increasing subsequence

300. The longest increasing subsequence

subject

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

Advanced ：

You can reduce the time complexity of the algorithm to O(n log(n)) Do you ?

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/longest-increasing-subsequence
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Answer key

Multistage decision making + Optimal solution , Try dynamic programming .

determine dp The meaning of array and its subscript
dp[i]: With nums[i] The length of the strictly increasing subsequence at the end is dp[i]

dp Array recursion
dp[i] The value of is in nums[i] The length of the strictly increasing subsequence at the end , So we need to i-1 Start looking forward nums[i] Small number nums[j], Than nums[i] There must be many small numbers , choice dp[j] The biggest one nums[j] Form a new strictly increasing subsequence .
If you don't find it, just nums[i] Start with a new strictly increasing subsequence .

for(let i=0;i<nums.length;i++){
    
    for(let j=i;j>=0;j--){
    
	    if(nums[j]<nums[i])dp[i] = Math. max(dp[i],dp[j]+1);     
    }
    res = Math.max(res,dp[i]);
}

dp Array initialization
dp The array is initialized to 1, It means to start with oneself 、 The length of the strictly increasing subsequence at its end is 1

let dp = new Array(nums.length).fill(1) ;

Code

var lengthOfLIS = function(nums) {
    
    let dp = new Array(nums.length).fill(1) ;
    let res = 1;
    for(let i=0;i<nums.length;i++){
    
        for(let j=i;j>=0;j--){
    
	        if(nums[j]<nums[i])dp[i] = Math. max(dp[i],dp[j]+1);     
       }
       res = Math.max(res,dp[i]);
    }
    
    return res;
};