Leecode-Go-最大子数组和（切片相关）

vlambda
2022-02-22

Leecode-Go-最大子数组和（切片相关）

给定一个整数数组nums，需要我们找出一个具有最大和的连续子数组（子数组最少包含一个元素），但是只需要返回其最大和，需要注意的是，子数组表示的是数组中的一个连续部分。

举个例子，比如说我们输入的内容是nums = [-2,1,-3,4,-1,2,1,-5,4]，那么我们输出的内容就应该是6。

那么我们来详细的分析一下，如下是我们利用滑动窗口算法之后，所有可以找到的子数组，以及聚合之后的结果，将结果对比后可得到上述答案：

可找到的所有子数组为：[-2] ，求和之后的值为：-2
可找到的所有子数组为：[1] ，求和之后的值为：1
可找到的所有子数组为：[-3] ，求和之后的值为：-3
可找到的所有子数组为：[4] ，求和之后的值为：4
可找到的所有子数组为：[-1] ，求和之后的值为：-1
可找到的所有子数组为：[2] ，求和之后的值为：2
可找到的所有子数组为：[1] ，求和之后的值为：1
可找到的所有子数组为：[-5] ，求和之后的值为：-5
可找到的所有子数组为：[4] ，求和之后的值为：4
可找到的所有子数组为：[-2 1] ，求和之后的值为：-1
可找到的所有子数组为：[1 -3] ，求和之后的值为：-2
可找到的所有子数组为：[-3 4] ，求和之后的值为：1
可找到的所有子数组为：[4 -1] ，求和之后的值为：3
可找到的所有子数组为：[-1 2] ，求和之后的值为：1
可找到的所有子数组为：[2 1] ，求和之后的值为：3
可找到的所有子数组为：[1 -5] ，求和之后的值为：-4
可找到的所有子数组为：[-5 4] ，求和之后的值为：-1
可找到的所有子数组为：[-2 1 -3] ，求和之后的值为：-4
可找到的所有子数组为：[1 -3 4] ，求和之后的值为：2
可找到的所有子数组为：[-3 4 -1] ，求和之后的值为：0
可找到的所有子数组为：[4 -1 2] ，求和之后的值为：5
可找到的所有子数组为：[-1 2 1] ，求和之后的值为：2
可找到的所有子数组为：[2 1 -5] ，求和之后的值为：-2
可找到的所有子数组为：[1 -5 4] ，求和之后的值为：0
可找到的所有子数组为：[-2 1 -3 4] ，求和之后的值为：0
可找到的所有子数组为：[1 -3 4 -1] ，求和之后的值为：1
可找到的所有子数组为：[-3 4 -1 2] ，求和之后的值为：2
可找到的所有子数组为：[4 -1 2 1] ，求和之后的值为：6
可找到的所有子数组为：[-1 2 1 -5] ，求和之后的值为：-3
可找到的所有子数组为：[2 1 -5 4] ，求和之后的值为：2
可找到的所有子数组为：[-2 1 -3 4 -1] ，求和之后的值为：-1
可找到的所有子数组为：[1 -3 4 -1 2] ，求和之后的值为：3
可找到的所有子数组为：[-3 4 -1 2 1] ，求和之后的值为：3
可找到的所有子数组为：[4 -1 2 1 -5] ，求和之后的值为：1
可找到的所有子数组为：[-1 2 1 -5 4] ，求和之后的值为：1
可找到的所有子数组为：[-2 1 -3 4 -1 2] ，求和之后的值为：1
可找到的所有子数组为：[1 -3 4 -1 2 1] ，求和之后的值为：4
可找到的所有子数组为：[-3 4 -1 2 1 -5] ，求和之后的值为：-2
可找到的所有子数组为：[4 -1 2 1 -5 4] ，求和之后的值为：5
可找到的所有子数组为：[-2 1 -3 4 -1 2 1] ，求和之后的值为：2
可找到的所有子数组为：[1 -3 4 -1 2 1 -5] ，求和之后的值为：-1
可找到的所有子数组为：[-3 4 -1 2 1 -5 4] ，求和之后的值为：2
可找到的所有子数组为：[-2 1 -3 4 -1 2 1 -5] ，求和之后的值为：-3
可找到的所有子数组为：[1 -3 4 -1 2 1 -5 4] ，求和之后的值为：3
可找到的所有子数组为：[-2 1 -3 4 -1 2 1 -5 4] ，求和之后的值为：1

到这里题意差不多都理解了，之后我们来看下最笨的解决方法：

package main
import "fmt"
func main() { nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4} fmt.Println(maxSubArray(nums))}
func maxSubArray(nums []int) int { var ( sign = 1 maxNum = 0 numsLen = len(nums) maxAry = make(map[int]int) )
 maxNum = nums[0] for sign <= numsLen { for i := 0; i < numsLen; i++ { if i+sign <= numsLen { sonNum := nums[i] for j := i + 1; j < i+sign; j++ { sonNum += nums[j] } fmt.Println("可找到的所有子数组为：", nums[i:i+sign], "，求和之后的值为：", sonNum) if _, ok := maxAry[sign]; ok { if maxAry[sign] < sonNum { maxAry[sign] = sonNum } } else { maxAry[sign] = sonNum } } }
 if maxNum < maxAry[sign] { maxNum = maxAry[sign] }
 sign++ }
 return maxNum}

上述方法就是我能给出的答案。

但肯定不是最好的，我顺手找了别的方案，希望可以给各位开拓一下思路：

package main
import "fmt"
func main() { nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4} fmt.Println(test(nums))}
func test(nums []int) int { numsLen := len(nums) maxNum := nums[0] for i := 1; i < numsLen; i++ { if nums[i-1] > 0 { nums[i] = nums[i] + nums[i-1] }
 if maxNum < nums[i] { maxNum = nums[i] } }
 return maxNum}

套用人家作者的原话，这种方式或者是思想可以理解为动态规划，nums[i-1]并不是数组前一项的意思，而是到前一项为止的最大子序和，和0比较是因为只要大于0，就可以相加构造最大子序和，如果小于0则相加为0，nums[i]=nums[i]，相当于最大子序和又重新计算，本质其实是一边遍历一边计算最大序和。

牛吧，我这种凡人根本没想到。。。

至此，本次分享就结束了，后期会慢慢补充。

以上仅为个人观点，不一定准确，能帮到各位那是最好的。

好啦，到这里本文就结束了，喜欢的话就来个三连击吧。

以上均为个人认知，如有侵权，请联系删除。

vlambda博客
学习文章列表