Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

Problem description

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:

Input: nums = [2,1,6,3,5,4]

Output: 3

Explanation: the longest increasing subsequence is [1,3,4] and therefore has a length of 3.

To analyze problems

For the length of the longest increasing sequence ending with the ith digit, it is equal to the maximum length of the longest increasing subsequence ending with the JTH digit +1, where 0<j< I, and nums[j] < nums[I]. For example, the length of the longest increasing subsequence ending in 5 is equal to the length of the longest increasing subsequence ending in 3 +1.

So, we define an array dp, where dp[I] represents the length of the longest increasing subsequence ending with the ith element. The state transition equation can be easily known as: dp[I]= Max (dp[j])+1, where 0<j< I and NUMs [j]<nums[I]. Consider adding an element nums[I] after the longest increasing subsequence in dp[0…i-1] so that the newly generated subsequence satisfies the increasing condition.

Finally, the length of the longest increasing subsequence of the entire array is the maximum in array DP.

Let’s look at the implementation of the code.

Def lengthOfLIS(nums): if not nums: return 0 dp = [] # for range(len(nums)): For j in range(I): if nums[I] > nums[j]: if nums[I] > nums[j]: Dp [I] = Max (dp [I], dp [j] + 1) return Max (dp) print (lengthOfLIS (,1,6,3,5,4 [2]))Copy the code

The time complexity is O(n^2), where n is the length of array nums. Because for each element of the array NUMS, we need O(n) time to traverse the elements in dp.

Space complexity is O(n), where n is the length of the array NUMs.

To optimize the

Here, too, we can use greedy thinking to solve. Since the problem is to find the longest increasing subsequence, to make the increasing subsequence long enough, we need to make the sequence rise as slowly as possible, so we want the number added to the end of the increasing subsequence to be as small as possible.

We maintain an array d, where d[I] represents the minimum of the trailing element of an increasing subsequence of length i. for example, for the sequence **[2,1,6,3,5,4], the subsequences 1,3,5 and 1,3,4** are the longest increasing subsequences, then d[3]=4, because 4<5.

At the same time, we can also notice that the array D is monotonically increasing, i.e. for j< I, then d[j]

=d[I], we consider deleting i-J elements from the end of the oldest sequence of length I, then the length of the sequence becomes J, and the JTH element x must be less than d[I] (since it is an increasing subsequence, d[I] comes after x, so d[I]>x). X
[i].>

We iterate through the elements of the array and update the values of arrays D and len. If nums[I] > d[len], len=len+1; otherwise, find the first number d[k] less than nums[I] and update d[k+1]=nums[I].

Def lengthOfLIS(nums): d = [] # def lengthOfLIS(nums): If not d or n > d[-1]: d.append(n) else: if not d or n > d[-1]: d.append(n) else: l = 0 r = len(d) - 1 k = r while l <= r: mid = (l + r) // 2 if d[mid] >= n: k = mid r = mid - 1 else: l = mid + 1 d[k] = n return len(d)Copy the code

The time complexity of this algorithm is O(nlogn). We iterate through nums and update array d with the elements in the array. When we update array d, we use binary search to locate the location to be updated, so the time complexity is O(nlogn). The space complexity is O(n) because you need an extra array D to hold it.

The advanced

Given an array nums of length n, print the longest increasing subsequence of nums. If there are more than one answer, print the one with the smallest numeric comparison lexicographical order.

Example:

Input:,2,8,6,4 [1]

Return value: [1,2,4]

Note: there are 3 longest increasing subsequences, (1,2,8), (1,2,6) and (1,2,4), among which the third one has the smallest lexicographical order by numerical comparison, so the answer is (1,2,4).

Maxlen (nums[I]) maxlen (nums[I]) maxlen (nums[I]) maxlen (nums[I])

After we have the array maxlen and array D, we know that the longest increasing subsequence of the sequence is len(d). If maxlen[I]=len(d), we will return the result res for the elements, and so on until the traversal is complete.

Tips: Why iterate through the maxlen group from back to front? Given that maxlen is [1,2,3,3,3], and the final output is res (the longest increasing subsequence with the smallest lexicographic order), then the position of the last element of res in nums is maxlen(I)==3 for the subscript I of, Nums [2], nums[3], and nums[4]. If it is nums[2], then nums[2] < nums[4], then maxlen[4]=4, which contradicts the known condition, so we should put nums[4] in the last position of res. So you have to go backwards and forwards.

Def lengthOfLIS(nums): def lengthOfLIS(nums): def lengthOfLIS(nums): maxlen = [] If not d or n > d[-1]: if not d or n > d[-1]: if not d or n > d Maxlen.append (len(d)) else: l = 0 r = len(d) -1 k = r while l <= r: mid = (l + r) // 2 if d[mid] >= n: k = mid r = mid - 1 else: Maxlen.append (k+1) = maxlen.append(k+1) = maxlen.append(k+1) = maxlen.append(k+1) Lens =len(d) res = [0] * lens for I in range(len(maxLen)-1,-1,-1): If maxLen [I]==lens: res[len-1]=nums[I] lens= len-1 return res print(lengthOfLIS([1,2,8,6,4])Copy the code

The time complexity of this algorithm is O(nlogn) and the space complexity is O(n).

The last

That’s it. We’re done talking about this topic.

Original is not easy, you think the article is good, might as well like, look at, forward three even go!

The more you know, the more your mind opens up. See you next time.