题目描述#
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
知识边界#
这道题主要涉及数组遍历、前缀和和最值维护。
1. 数组与切片#
在 Go 中，这类题通常使用切片 []int 表示整数序列。
例如：
nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}常见遍历方式：
for i := 0; i < len(nums); i++ {
fmt.Println(nums[i])
}
for _, n := range nums {
fmt.Println(n)
}本题使用的是 for _, n := range nums 这种写法，适合顺序扫描数组中的每个元素。
2. 前缀和#
前缀和表示从数组开头到当前位置的元素总和。
设：
prefix[i]表示前i个元素的和
那么任意连续子数组 nums[l...r] 的和可以表示为：
prefix[r+1] - prefix[l]这就是本题做法的核心。只要我们在遍历到某个位置时，知道此前最小的前缀和，就可以立刻算出“以当前位置为右端点”的最大子数组和。
3. 最小前缀和维护#
代码中有三个关键变量：
prefix：当前前缀和premin：遍历过程中出现过的最小前缀和premax：当前找到的最大子数组和
核心过程是：
- 先更新当前前缀和
- 用
prefix - premin计算当前位置能得到的最大连续子数组和 - 再更新最小前缀和
因为固定当前右端点时，减去越小的前缀和，得到的区间和就越大。
4. Go 中的 math.MinInt#
代码中使用了：
premax := math.MinInt这样做是为了保证即使数组中的元素全是负数，也能正确得到答案。
例如：
nums := []int{-3, -2, -5}最大子数组和应该是 -2，如果把初始值写成 0，就会出错。
需要注意导入：
import "math"5. 特殊情况处理#
单独处理了：
if len(nums) == 1 {
return nums[0]
}虽然这道题也可以不单独写这个分支，但按照当前代码逻辑保留这个判断，可以让单元素数组直接返回结果，逻辑更直接。
6. 常见错误点#
错误一：把答案初始值写成 0#
如果数组全为负数，答案不一定是 0，而应该是其中最大的那个负数。
错误二：更新顺序写错#
这里必须先：
prefix += n然后用：
prefix - premin更新答案，最后再更新 premin。
如果顺序写错，可能会把当前前缀和错误地提前纳入最小前缀和中，影响结果。
错误三：把子数组理解成不连续的序列#
题目要求的是连续子数组，不允许跳过元素。
思路#
这道题按照你的代码思路，使用的是前缀和 + 历史最小前缀和的方法。
思路一#
设当前前缀和为 prefix。
对于任意一个以当前位置结尾的连续子数组，它的和都可以表示为：
当前前缀和 - 某个之前位置的前缀和如果想让这个值最大，那么减去的那个前缀和就应该尽可能小。因此在遍历数组时，我们维护一个变量 premin，表示到目前为止最小的前缀和。
同时维护：
premax：当前找到的最大子数组和prefix：当前前缀和
遍历每个元素 n 时：
- 把
n加到prefix - 计算
prefix - premin，尝试更新premax - 如果当前
prefix更小，就更新premin
你的代码中还额外处理了 len(nums) == 1 的情况，这样单元素数组可以直接返回。
为什么这样做是正确的#
因为任意连续子数组都可以表示成两个前缀和之差。
当我们固定右端点时，子数组和是否最大，取决于左端点之前的前缀和是否最小。只要在扫描过程中持续维护“历史最小前缀和”，就能保证每次都找到当前右端点对应的最优子数组和。再在这些局部最优中取最大值，就得到全局最优答案。
时间复杂度#
O(n)。
整个数组只遍历一次，每个元素只进行常数次操作。
空间复杂度#
O(1)。
只使用了 premax、premin 和 prefix 三个额外变量。
代码#
package main
import "math"
func maxSubArray(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
premax := math.MinInt
premin := 0
prefix := 0
for _, n := range nums {
prefix += n
if prefix-premin > premax {
premax = prefix - premin
}
if prefix < premin {
premin = prefix
}
}
return premax
}