“This is the second day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

Longest increasing subsequence

Power button link

Given an integer array nums, find the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from an array that deletes (or does not delete) the elements of the array without changing the order of the rest of the elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

Input: nums = [10,9,2,5,3,7,101,18] output: 4 explanation: the longest increasing subsequence is [2,3,7,101], so length is 4.Copy the code

Example 2:

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

Input: nums = [7,7,7,7,7] Output: 1

Tip:

1 <= nums.length <= 2500 -104 <= nums[i] <= 104  

Advanced:

Can you design a solution with O(n2) time? Can you reduce the time complexity of the algorithm down to order n log n?

Dynamic programming

Train of thought

Here we use the idea of dynamic programming to achieve, here for easy understanding, with my vernacular to explain.

Important points: Assume that nums length is N; F (n) is the value of the longest increasing subsequence. If nums[n+1]>nums[n] then fn(n +1) = fn(n)+1

And when we do this, we can assume that if there’s only one element, then its longest increasing subsequence must be 1. We use an array dp as long as nums, nums from length 0 to length length-1, and the maximum number of sequences for each length (denoted as dp[I]).

That is, dp[0] =1 when len of NUMs =1. When nums is increased by 1, the latest digit is compared to the previous digit. If the value is greater than the previous digit (for example, nums[1]>nums[0]) then dp[1] = math.max (dp[I],dp[0]+1). The maximum value is taken because the new value may be larger than the previous value in multiple locations, and the longest increasing subsequence (dp[I]) corresponding to each length is different. Record the maximum value at the end of the cycle, and then return

var nums = [10.9.2.5.3.7.101]
    var lengthOfLIS = function(nums) {
        if(nums.length===1) return 1
        var dp = [];// The maximum value for each length
        var maxLen = 1
        dp[0] = 1
        for(var i=0; i<nums.length; i++){ dp[i] =1
            for(var j=0; j<i; j++){if(nums[i]>nums[j]){
                    dp[i] = Math.max(dp[i],dp[j] + 1)
                }
            }
            maxLen = Math.max(maxLen,dp[i])
        }
        return maxLen
    };
    console.log(lengthOfLIS(nums))
Copy the code