Algorithm interview Replay: Longest ascending subsequence (bytes)

In the last article, we learned what DP (dynamic programming) is and how state transition equations should be defined by the classic problem “maximum suborder sum” in DP. In this section, we will use the previous analysis method, through an example, to further consolidate the previous content!

01. Topic analysis

Example:

Input: [10,9,2,5,3,7,101,18] output: 4 explanation: the longest ascending subsequence is [2,3,7,101], which has a length of 4.Copy the code

Description:

• There can be multiple combinations of the longest ascending subsequence, and you just output the corresponding length.

This problem has certain difficulty oh! If you do not have ideas, please review the last learning content! It is not recommended to read the problem directly!

02. Title Diagram

First of all, we analyze the topic, and we want to find the Longest Increasing Subsequence (LIS). Since continuity is not required in the problem, LIS may be continuous or discontinuous. At the same time, LIS meets the condition that it can be constructed from the optimal solution of its subproblem. So we can try to solve it with dynamic programming. First we define the state:

Dp [I] : represents the length of the longest ascending subsequence ending in nums[I]

We assume that nums is [1,9,5,9,3] as shown below:

We will discuss it in two cases:

• If nums[I] is smaller than all the preceding elements, then dp[I] is equal to 1 (itself).
• If nums[I] is preceded by the element nums[j], then dp[I] is dp[j]+1.

May include nums[k], nums[p], and so on, in addition to NUMs [j]. So dp[I] could be dp[k]+1, dp[p]+1, etc., etc. So we need to find the maximum of dp[j]+1, dp[k]+1, dp[p]+1, and so on. (I made bold on 3, etc., etc., mainly because it’s very easy for beginners to fall over here! The purpose of emphasis here is to remember this question type! That is:

Dp [j]+1, dp[k]+1, dp[p]+1,…..
Just meet:
nums[i] > nums[j]
nums[i] > nums[k]
nums[i] > nums[p]
.

After analysis, we drew a graph:

03. Examples of Go language

According to the above analysis, the code can be obtained as follows:

func lengthOfLIS(nums []int) int {
	if len(nums) < 1 {
		return 0
	}
	dp := make([]int.len(nums))
	result := 1
	for i := 0; i < len(nums); i++ {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				dp[i] = max(dp[j]+1, dp[i])
			}
		}
		result = max(result, dp[i])
	}
	return result
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
Copy the code

I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download