Hello, I come again, today to bring you an Easy topic, the largest suborder and, can also be involved in the dynamic planning ideas, so nonsense not to say, follow my train of thought go!

So let’s look at the problem as usual

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

“Example“

Input: [-2,1, -1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.Copy the code

Given an array, find the largest sum of the elements in the subarrays of the array. This is the idea of using “Dynamic Programming”. Let’s take an example

Now there are nine arrays in the array, so how do we know what the largest sum of these nine numbers is? Don’t know? That’s okay. What if there were only eight? Seven? 6? . 1?

If the largest sum of an element is itself, right? The idea of dynamic programming is that

1. Delimiter problem
2. Results the reuse

So let’s draw a picture to explain!

We know that the maximum sum of arr[0] is -2, so we can deduce that “the maximum sum of arr[1] is arr[0]+arr[1]”. However, we need to consider a question: “Is arr[0]+arr[1] the maximum?”

The obvious answer is that arr[0]+arr[1] = -1, so the largest sum of arr[1] should be itself, since 1 is greater than -1. So let’s go with the idea that if we derive all the next nine numbers, we’ll get the following array

You get a number, every value in dp, is the optimal solution to dp[I minus 1], so the optimal solution means choice, so how do you refer to choosing or not choosing? That’s what dynamic programming does

So let’s say we want the value of F of 3

This is a formula“f(i) = max(f(i-1), 0) + f(i)“It doesn’t matter if you don’t understand, the main thing is multiple derivation

So at this point, do we have to have an array to hold the sum of all the subarrays? Isn’t that a waste?

It looks like we just need to save the largest sum of the last one, right, because every time we compare “f(I)” to “f(I -1” so why do I open an array? A waste!

Now, let’s look at the super simple version, where you can do this with just one variable, two variables

func maxSubArray(nums []int) int {
	if len(nums) == 1{
		return nums[0]
	}
	max := nums[0]
	last := nums[0]
	for i:=1; i< len(nums); i++{
		last = Max(nums[i], last+nums[i])
		max = Max(last, max)
	}
	return max
}
func Max(x, y int) int{
	if x > y{
		return x
	}
	return y
}
Copy the code

One method Max is used to find the maximum, what’s the big deal about that

Let’s look at these two important points

last = Max(nums[i], last+nums[i])
max = Max(last, max)
Copy the code

Is the current value of “f(I)” greater than “last(last maximum sum)+f(I)”? If so, the current value of “f(I)” is the maximum sum; otherwise, **last+f(I)** is the maximum sum

Next, we need to update the sum of the largest subsequence, which is the comparison between “last” and the current “Max”. If it is large, we take the largest value as the sum of the current largest subsequence and return it

Here, the end, the most important thing is that we practice more, do not simply finish reading do not do, come on

Other related topics link

LeetCode 49 – Letter heterotopic word grouping – Solution record – Golang

LeetCode 21 – Merge ordered lists – Solution record – GoLang

LeetCode 2 – Sum of two numbers – GoLang

LeetCode 12 – Roman numerals – GoLang

LeetCode 15-3 number sum – GoLang

LeetCode 5 – Palindrome string – Solution idea record – GoLang