package dynamic_programming

import "leetcodes/common"

/**
53. 最大子序和

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [0]
输出：0

示例 4：
输入：nums = [-1]
输出：-1

示例 5：
输入：nums = [-100000]
输出：-100000

提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
*/

func maxSubArray(nums []int) int {
	// 初始化 当前和 以及 最大和 两个遍历
	currSum := nums[0]
	maxSum := nums[0]
	// 遍历切片，其中 i != 0 是为了防止越界
	for i, n := range nums {
		if i != 0 {
			// 维护 当前和 的最大值
			currSum = common.GetMax(n, currSum+n)
			// 维护 最大和，取 当前和 与前一个 最大和 中的最大值
			maxSum = common.GetMax(currSum, maxSum)
		}
	}
	return maxSum
}