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


Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.


The question to describe

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.

Example 2:

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

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

Analysis of the

This is probably a very, very classic problem type, and there are two ways to do this, one is DP, which is dynamic programming, and the other is binary search.

Solution 1: DP

Idea: let’s go to maintain an additional array, the array to store the longest increasing sequence, if you want to insert data cannot pose the greatest increasing subsequence, so can’t insert, but later may have longer sequences, so while maintaining the original array is still the biggest put 4 in under the condition of increasing sequence, also is the updated 3 to 4, Prepare for maximally increasing sequences that may occur later.

var lengthOfLIS = function(nums) {
    const dp = new Array(nums.length)
    dp[0] = 1

    // Step 1: calculate the corresponding length of dp[I]
    for(let i = 1; i < dp.length; i++) {
        // Find the maximum dp value that is less than nums[I]
        let j = 0
        let belowMaxDP = 0
        while (j < i) {
            if (nums[j] < nums[i] && dp[j] > belowMaxDP) {
                belowMaxDP = dp[j]
            }
            j++
        }
        dp[i] = belowMaxDP + 1
    }
    let max = 1
    let i = 0
    while (i < dp.length) {
        if (dp[i] > max) {
            max = dp[i]
        }
        i++
    }
    return max
};

Copy the code
Solution 2: DP+ dichotomy

Idea: Add two points to the previous idea to improve efficiency.

var lengthOfLIS = function(nums) {
    const dp = new Array(nums.length).fill(0)
    let len = 0
    for(let i = 0; i < nums.length; i++) { let ind = binarySearch(dp,0, len, nums[i])
        if(ind < 0) ind = -ind
        dp[ind] = nums[i]
        if(ind === len) len++
    }
    return len
};

function binarySearch(arr, from ,to, target){
    if(to === 0) return -0
    if(target < arr[from]) return -from
    if(target > arr[to - 1]) return -to
    let l = from
    let r = to
    while(l < r) {
        const mid = Math.floor((l + r) / 2)
        if(target > arr[mid]) {
            l = mid + 1
        } else if(target < arr[mid]) {
            r = mid
        } else {
            l = mid
            r = mid
        }
    }
    return arr[l] === target ? l : -l
}
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤