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

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

At first glance, I thought this problem was the longest continuous increasing subsequence, so I thought it would be better to just use a loop. Later, I found that the answer was wrong, so I looked at the problem again, only to find that it was much more complicated than I expected.

Because each step needs to consider the optimal solution of the previous step, take Example 1

Nums = [10,9,2,5,3,7,101,18] when we traverse to 10,9, 3,7,10, and 2, since the latter are all smaller than the former, the length of the sequence of the oldest group at this time is 1. At this time, we mark the heads of 10,9, and 2 with 1. When we traverse to 5, we traverse again to 5, since 2 is smaller than 5. 2 head is 1, so should be 2, 5 head because of the increasing subsequences of 2, 5, by the same token, the head is 2, and 3 when we traverse to 7, we again from the beginning through to July, when the second traversal to 5, with 5 head is 2, so the value of the 7 head grow to 3, the same time continue to traverse, We're going to have a value at the head of each number, which is the maximum number of longest increasing subsequences of that number, and find that maximum, which is the maximum number of longest increasing subsequences of that array.Copy the code

Convert to code for

Var lengthOfLIS = function (nums) {var lengthOfLIS = function (nums) {let dp = []; Dp [0] = 1; // let maxAns = 1; for (let i = 0; i < nums.length; I ++) {dp[I] = 1 for (let j = 0; j < i; J ++) {// if nums[I] is larger than nums[j] If (nums[j] < nums[I]) dp[I] = math. Max (dp[I], MaxAns = max. Max (maxAns, dp[I])} return maxAns};Copy the code

So this is our time order n squared, so can we reduce it to order nlogn, when we see logn, the first thing that comes to mind is dichotomy, and dichotomy is the most common way to find the right element, and when do we find the right element in this problem, we’re going to think, When iterating to 7, do we need to judge [2,3] and judge [2,5] again? Can we judge [2,3] once? Because if [2,3,7] is true, then [2,5,7] must be true, so we only need to change the value of each position to the minimum value that should be at this position. You don’t have to go forward every time, you just have to record the previous optimal subsequence.

So we need to think differently. Take example 1 as an example

Nums = [10,9,2,5,3,7,101,18]; nums = [10,9,2,5,3,7,101,18]; nums = [10,9, 3,7,10,18]; Since 5>3, consider replacing 5 with 3 because if it is the longest increment, the increment of each increment is as small as possible [2,3], and finally output [2,3,7,101],length=4Copy the code

Let’s look at another example

Nums = [10, 9, 2, 11, 22, 33, 44, 3,7, 5, 101, 18] we continue to push the smallest number first and back [2, 11, 22, 33, 44] since subsequent numbers are not as large as 44, so we replace them when 3,7 is encountered. ,3,7,33,44 [2]. I'm sure there are a lot of people like me at this point, why 3 and 7 can be inserted into the stack, obviously changing the order. Because here we only need to get the maximum length of the subsequence, if 3,7 is not added to the stack, but a new stack is created, it becomes [2, 11, 22, 33, 44],[2,3,7]. Is still the first array length is longer, does not affect the result of calculation, but if the back to join the second array number more than the first array, at this time will affect the result, but at this stage, you will find, if after replacement, the second array will completely replace the first array, it still will not affect the final result, So if it encounters an element larger than the top of the stack, it is added to the stack, and if it encounters an element smaller than the top of the stack, it finds a suitable place in the stack to replace it. Finally, the maximum increment subsequence of the array becomes [2,3,5,33,44,101], with length 6Copy the code

Let’s switch to code

Var lengthOfLIS = function (nums) {var lengthOfLIS = function (nums) {let len=1, n= nums.length; if (n == 0) return 0; // let d = []; D [len] = nums[0]; For (let I = 1; i < n; If (nums[I] > d[len]) {d[++len] = nums[I]} else { Let l = 1, r = len, pos = 0; While (l <= r) {let mid = math.floor ((l + r) / 2); let mid = math.floor ((l + r) / 2); if (d[mid] < nums[i]) { pos = mid; L = mid + 1} else {r = mid-1}} d[pos + 1] = nums[I]}}Copy the code