53. 最大子数组和

最新推荐文章于 2025-12-12 16:31:11 发布

原创最新推荐文章于 2025-12-12 16:31:11 发布 · 144 阅读

0 ·

CC 4.0 BY-SA版权

文章标签：

#算法 #leetcode #go

leetcode-go 专栏收录该内容

14 篇文章

订阅专栏

https://leetcode.cn/problems/maximum-subarray

解题思路：
使用贪心思想，我们加入一个新元素时希望当前的子数组和为正数，如果不为正数那么我们就舍弃之前的子数组重新开始。

func maxSubArray(nums []int) int {
	r := 1
	maxSum, currSum := nums[0], nums[0]
	for r < len(nums) {
		// 如果当前子数组和为负数，则舍弃之前的子数组重新开始
		if currSum <= 0 {
			currSum = nums[r]
		} else { // 如果当前子数组和为正数，则继续累加
			currSum += nums[r]
		}
		maxSum = max(maxSum, currSum)
		r++
	}
	return maxSum
}