“This is the 14th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

First, an appetizer. Given an unsorted array of integers, find the longest continuously increasing subsequence and return the length of that sequence.

Nums = [1,3,5,4,7] // the longest continuous increasing sequence is [1,3,5] with length 3.Copy the code

  • We first analyze continuous increment I > 0 && nums[i-1] <= nums[I] // start position greater than 0 is currently larger than the previous bit or equal to constitute continuous increment

  • Then record the length at this time i-start+1, we want to save the temporary length ans, and compare it to the previous length to take the maximum math.max (ans, i-start+1), at the end of the loop will be our maximum length.

// Complete the code
let start = 0
let ans = 0
for(let i = 0; i< nums.length; i++){
    if(i>0 && nums[i]<= nums[i-1]){
        start = i
    }
    ans = Math.max(ans, i-start +1)}return ans
Copy the code

Now let’s go to the analysis of leetcode300. Given an integer array nums, find the length of the longest strictly increasing subsequence.

  • The longest strict increment can only be greater than the preceding one, equal does not count

  • We use dynamic programming

  • So let’s initialize onedpEach element of the array is1.
  • The outer loop uses a temporary variablemax, takeMath.max(dp[i], max)
  • And then compare it from index I -1

Max (dp[I],dp[j] + 1)

 // Complete the code
 // Determine the boundary
const n = nums.length 
if(n <= 1) {return n
}
let max = 0
const dp = new Array(n).fill(1) / / initialization
for(let i = 1; i < n; i++){
    for(let j = i-1; j>=0; j--){
        // Strictly incrementing
        if(nums[i] > nums[j]){
            Dp [j] +1 = nums[I] +1 = nums[I
            dp[i] = Math.max(dp[i], dp[j] + 1)
        }
    }
    max = Math.max(d[i], max)
}
return max
Copy the code

In the above solution, the current element is compared to the previous element, so if you keep a record, you don’t need any more comparisons

  • Optimized solution, define adp[i]Record a value of lengthiThe minimum value of the element at the end of the longest increasing subsequence
  • dp[1]Initialize thenums[0]
  • ifdpAll of the elements in thenums[i], insert it to the end
  • Otherwise binary search dp, usenum[i]Overwrite anything larger than it

const n = nums.length;
let max = 1
if(n <=1 )return n
const dp = [null, nums[0]]
for(let i = 1; i< n; i++){
    if(dp[max] < nums[i]){
        dp[++max] = nums[i]
    }
    // Binary search
    let left = 1,
    right = max,
    mid,
    pos = 0
    while(left <= right){
        mid = (right+left )>>1
        if(dp[mid] < nums[i]){
            / / on the left
            left = mid+1
            pos = mid
        }else{
            right = mid-1}}// Replace the one larger than the current element
    dp[pos+1] = nums[i]
}
return max
Copy the code

Conclusion: Dp is used to record the minimum value of the tail element of a longest increasing subsequence with length I, which can reduce the number of comparisons and optimize the time complexity O(nlogn).