Shulou(Shulou.com)06/02 Report--

This article shows you how to use leetcode continuous series in golang, the content is concise and easy to understand, it will definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

Given an array of integers (positive and negative), find the contiguous sequence with the largest sum and return the sum.

Example:

Input: [- 2, 1, 1, 4, 4, 1, 2, 1, 2, 1, 5, and 4]

Output: 6

Explanation: the sum of the continuous subarray [4 mai Yu 1 JI 2 Jue 1] is the largest, which is 6.

Advanced:

If you have implemented a solution with a complexity of O (n), try to use a more subtle divide-and-conquer method.

Problem-solving ideas

Solution 1 (dynamic programming)

Suppose the array name is arr and the resulting array is result

When there is only one number, the largest consecutive sequence can only be this number, so where the sequence number is 0 and the maximum value is-2, then result [0] = arr [0]

When there are two numbers, there are two situations.

Keep the previous sequence, and the value is result [0] + arr [1] =

The previous sequence is not retained, and the current value is 1, that is, arr [1]

If the maximum value is selected at this time, it is 1.

By the third number,

Keep the previous sequence with a value of result [1] + arr [2] = 1 +-3 =-2

The previous sequence is not retained, and the value is arr [2] =-3

If the maximum value is selected at this time, it is-3.

And so on, you can get the following table.

Serial number 012345678 (arr array)-21-34-121-54 preserves the previous sequence

-1-4-135615 does not retain the previous sequence

1-34421-54 maximum (result array)-21-3445614

In summary, the following rules can be obtained.

In the end, only the number with the highest median value of result [] is the result.

Code public static int maxSubArray (int [] arrs) {

Int len = arrs.length

Int maxNum = arrs [0]

Int [] result = new int [arrs.length]

Result [0] = maxNum

For (int I = 1; I

< len; i++) { int a = result[i - 1] + arrs[i]; //保留前边的序列 int b = arrs[i]; //不保留前边的序列 int curMax = Math.max(a, b); result[i] = curMax; if (curMax >

MaxNum) {

MaxNum = curMax

}

}

Return maxNum

} Code Optimization

Since the result array is created in the above process, but in fact there is no other use after the current number is calculated in each loop, you can use the arrs array as the result array here, optimized as follows

Public static int maxSubArray (int [] arrs) {

Int len = arrs.length

Int maxNum = arrs [0]

For (int I = 1; I

< len; i++) { int a = arrs[i - 1] + arrs[i]; //保留前边的序列 int b = arrs[i]; //不保留前边的序列 int curMax = Math.max(a, b); arrs[i] = curMax; if (curMax >

MaxNum) {

MaxNum = curMax

}

}

Return maxNum

}

Code implementation

Func maxSubArray (nums [] int) int {sum:=0max:=0for iMagneur else range nums {max=n sum=n continue} if sum+n > n {sum+=n} else {sum=n} if max

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.