First from clap resist pressure!

To the chase

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,,6,2,7 [3]Is an array,3,1,6,2,2,7 [0]Subsequence of.

Concept:

Subsequence: A subsequence does not require continuity relative to a string, as in,5,2,3,4 [1], so 1, 2, 3, and 4 are subsequences. Even with a 5 in between, they are still sequence subsequences.

Strictly increasing: Strictly increasing means that the elements in sequence must be increasing without equality, as in:[1, 2, 3, 4]Is strictly increasing.,2,2,3,4 [1]Nonstrict increment

Such a requirement if the use of enumeration brute force cracking seems to be able to achieve the purpose, but the details require too much, and the complexity is too high, consumption performance is great, so no brute force cracking algorithm research.

Analysis:

In the picture above, for example,

At a glance, starting with 10, there are:

10,101 length 2 10,18 length 2 9,101 length 2 9,18 length 2 2,5,7,101 length 4, 2,5,7,18 length 4, 2,3,7,101 length 4, 2,3,7,18 length 4.. , etc.Copy the code

So by the time I get to 101, it’s probably at most 4. By the time the element 18 is reached, the maximum possible length is 4. The problem can be accomplished by recording the maximum possible sequence lengths to reach each element and then comparing the sizes of these lengths

How do I calculate the maximum possible length to reach each element?

The answer: dynamic programming!

The basic concept of dynamic programming: dynamic programming process is that every decision depends on the current state, and then causes the state transition. A decision sequence is produced in the changing state, so the process of multi-stage optimization decision solving problem is called dynamic programming.

How to implement dynamic programming

Create an array dbList of the same size as the target array, with each element having a value of 1, because by default each element is itself a subsequence of length 1 before it is evaluated and iterated

The dpList value is changed through the inner and outer loops in pairs, that is, the maximum length needed to reach the element.

Dynamic programming diagram:

The GIF is a bit long, so after watching it, you should have a certain understanding of dynamic programming!

Code implementation:

/** * @param {number[]} nums * @return {number} */ var lengthOfLIS = function (nums) { let dp = new Array(nums.length).fill(1) for (let i = 1; i < nums.length; // const right = nums[I] for (let j = 0; j < i; Const left = nums[j] if (left < right) {dp[I] = math.max (dp[I], Dp [j] + 1)}}} return math.max (... Dp) // get maximum length}; console.log(lengthOfLIS([0, 1, 0, 3, 2, 3]))Copy the code