essay
hot100-最大子数组和
#算法
hot100——最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
解
Kadane 算法核心思想
“如果当前累加和变成负数，就丢弃前面的所有，从下一个元素重新开始。”
为什么？
负数前缀只会拉低后续总和
任何以负数开头的子数组，都不如直接从后面正数开始
解1:
func maxSubArray(nums []int) int {
result := nums[0]
sum := 0
for _, num := range nums {
sum += num
result = max(result, sum)
// 如果当前和为负，就放弃前面所有
if sum < 0 {
sum = 0
}
}
return result
}
// 解2:
// func maxSubArray(nums []int) int {
// // 核心：result = sum[i] - minSum（当前前缀和 - 历史最小前缀和）
// sum := 0
// minSum := 0
// //防止数组只有一个元素（且为负），所以这个位置不能初始化为0
// result := nums[0]
// for _, num := range nums {
// sum += num
// result = max(result, sum - minSum)
// minSum = min(minSum, sum)
// }
// return result
// }