题目
给定一个数组 nums，找到一个连续子数组，其和最大，返回这个结果。
解析
从左往右遍历，我们分析一下数组的值变化情况
- 当遍历到一个正值的时候，这个值无论如何也是比当前值大的，直接更新当前最大值即可
- 当遍历到一个负值的时候，数组开始减小了，此时我们判断积累的值和上一个最大值哪个大，然后更新最大值。
- 如果累加值已经小于 0 了，那么再使用累加值和任意数相加都会更小，所以需要将累加值置空。
那么我们得到解体思路
- 一直累加 cur ，并更新最大值
- 一旦 cur 小于0，重置 cur 为 0
伪代码
for i < len
cur+=nums[i]
if cur < 0
cur = 0
代码
func maxSubArray(nums []int) int {
sum := -1<<63
cur := 0
for i:=0;i<len(nums);i++{
cur +=nums[i]
if cur > sum {
sum = cur
}
if cur < 0 {
cur = 0
}
}
return sum
}
网友评论