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

[topic address]

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: 4Copy the code

Example 3:

Input: nums = [7,7,7,7,7] Output: 1Copy the code

Tip:

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

Advanced:

  • You can design the time complexity to be zeroO(n2)Is the solution?
  • You can reduce the time complexity of the algorithm toO(n log(n))?

The problem is to find the longest increasing subsequence, then related to the optimal solution of the problem, generally the first thought of the solution method is dynamic programming

When it comes to dynamic programming, I want to talk about two concepts

State definition

The so-called state definition is described by a function symbol F (x) and the corresponding meaning of the function symbol, and the corresponding value of the function symbol is the value of the required solution

If you’re not familiar with dynamic programming, you probably don’t know what a state definition is, so let’s use this as an example to see how to define a state. Okay

First let’s consider a question: what does the value of the longest increasing subsequence depend on?

A: In this case, the value of the uppermost sequence is only related to the current subscript position

Let’s think about it, if we’re currently at subscript 0, the length of the longest increasing subsequence will be 1, and so on, the length of the longest increasing subsequence will change as the subscript position changes

So we define dp[I] as the length of the longest increasing subsequence at the subscript I position

Now let’s see what is a state transition equation

State transition equation

We know that dp[I] is the length of the longest increasing subsequence at subscript I, but the value at subscript 0 is simply 1, but what is dp[nums.length-1]?

That’s what the transition equation does

So let’s think about what is the condition for the longest increasing subsequence?

If the subscript of the following element is I and the subscript of the preceding element is j, then j < I && nums[j] < nums[I]

Dp [I] = dp[j]+1

So we just need to find all j positions that satisfy the condition before I, so that dp[I] is equal to the maximum value of all dp[j] that satisfy the condition +1

These are the two steps of dynamic programming

Answer key 1

var lengthOfLIS = function(nums) { const len = nums.length, dp = Array(len).fill(1); for(let i = 1; i<len; i++){ for(let j = 0; j<i; j++){ if(nums[j]<nums[i]) dp[i] = Math.max(dp[i],dp[j]+1) } } return Math.max(... dp) };Copy the code

The commit passed in about 190ms, beating only about 50% of users in terms of time, O(n²)

Answer key 2

As a pursuing front end, I was definitely not satisfied with the efficiency of solving the above problems, so I spent a whole afternoon of fragmentation time thinking about whether there was a better solution, and finally GAVE up the next morning

At this stage, the level is limited, I did not think of a better solution, and dynamic programming is just beginning to learn, so I can only reluctantly go to see the big man’s problem solving reference problem solving

By the way, I usually don’t watch the instructions first, but I get the code, it works fine, and I understand the code myself

I feel that if I have a process of understanding by myself, I will have a deeper impression. Moreover, since I understand something by myself, I can easily recall it when I look back after a period of time

Of course, if you encounter problems or have your own understanding in the process of understanding, you will still go to see the explanation, the former to solve the problem, the latter to compare your understanding is correct

So next I will explain the process and the original problem solution is not quite the same, interested partners can go to see the original problem solution, by the way to help the big guy give a thumbs up, leave a message, draft don’t forget the digging well!

Let’s look at nums = [10,9,2,5,3,7,101,18] given in example 1

We want to find the longest increasing subsequence in this array. If we convert the size of the element value to the height, the above array looks like this

Nums = [0,1,0,3,2,3] as shown in example 2:

So the longest increasing subsequence that we want to find is the longest continuous ascending ladder, and the longest increasing subsequence that we want to find in a graph like this is to kill off the columns, the elements, that violate that property.

So how do you do that?

If the front column is larger than it, it replaces the front column. If the front column is not larger than it, it is placed behind the front column. In order to ensure that we find the longest ascending ladder, we replace the left column first

The procedure for example 1 is as follows:

10
9
2
2 5
2 3
2 3 7
2 3 7 101
2 3 7 101 18
Copy the code

The procedure for example 2 is as follows:

0
0 1
0 1
0 1 3
0 1 2
0 1 2 3
Copy the code

Finally, the number of columns is the length of the longest increasing subsequence

So why does this process make sense to get the longest ascending subsequence?

Because we traverse the elements from left to right, from subscript 0 to the end of the array, the subscripts must be in order as the columns are arranged from low to high

And because we put the tall column behind the short column, the height of the column, the size of the element value, is also ordered

Maybe we ended up with a column that wasn’t a set of ladder columns corresponding to the original array, because the columns that were later updated didn’t completely cover the previous set of columns

I know it would have been better to animate it, but I don’t have any gifs at this stage because of the limitations, but we can use element values to represent the whole process

Note: Because the back column is covering the front column, the composition process in this example is bottom-up

Take example 1 as an example

2, 3, 7, 18 is a step 2, 3, 7, 101 is a step 2, 5, 9, 10Copy the code

Take example 2 as an example

0, 1, 2, 3 is going to be a step 0, 1, 2 is going to be a step 0, 1, 3 is going to be a step 0, 1, 0, 1Copy the code

Take the array [10,9,2,5,3,101,18,7,1,2]

Step 1, 2, 7 and step 1, 3, 7 will be completed once. Step 2, 3, 18 will be completed once. Step 2, 3, 101 will be completed onceCopy the code

Take the array [10,9,2,5,3,18,7,1,2,101]

Step 1, 2, 101 will be completed once, step 1, 2, 7 will be updated next time, step 1, 3, 7 will be updated next time. Step 2, 3, 7 will be completed once. Step 2, 3, 18 will be completed onceCopy the code

I’ll update the animation when it comes out

The code is as follows:

var lengthOfLIS = function(nums) { const pillars = [nums[0]]; let num = 1; for(let i = 1; i<nums.length; i++){ let cur = nums[i],l = 0,r = num-1; Pillars [r] {pillars[num] = cur; num++; While (l<r){const mid = (l+r) >> 1; if(pillars[mid]<cur) l = mid+1 else if(pillars[mid]>cur) r = mid else l = r = mid; } pillars[l] = cur; }} return num; };Copy the code

It took about 70ms to commit, beating 90+% of users, and the time complexity was O(nlogn)

Finally, HAVE a great weekend! But remember to study too!

If you have any questions or suggestions, please leave a comment!