最大子数组和（LeetCode 53）
1.问题描述
给你一个整数数组 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] <= 1042.难度等级
Medium。
3.热门指数
★★★★☆
4.解题思路
4.1 暴力
其实我们可以很容易设计出一个暴力的方法来求解本题，即简单地尝试所有子数组。
假设数组长度为 n，那么当子数组长度大于 1 时，共有
个。
当子数组长度等于 1 时，共有 n 个子数组。
因此其时间复杂度为
。
func maxSubArray(nums []int) int {
max := math.MinInt
for i := 0; i < len(nums); i++ {
sum := 0
for j := i; j < len(nums); j++ {
sum += nums[j]
if sum > max {
max = sum
}
}
}
return max
}4.2 分治
分治法求解最大子数组和可以提高效率。
假设寻找数组 A[low,high] 的最大子数组。使用分治意味着我们要将数组划分为两个规模尽量相等的子数组。也就是说，找到子数组的中间位置 mid，将数组分为两部分。
那么任何连续子数组 A[i,j] 所处的位置必然是以下三种情况之一：
（1）完全位于左边，low <= i <= j <= mid。
（2）完全位于右边，mid < i <= j <= high。
（3）跨越中间点，low <= i <= mid < j <= high。
对于 A[low,mid] 和 A[mid+1,high] 可以递归分治求解，因为这两个子问题仍是最大子数组问题，只是规模更小。因此，剩下的工作就是寻找跨越中点的最大子数组，然后在三种情况中选取和最大者。
如何找到跨越中点的最大子数组，很简单，我们只要以 mid 为起点，向左遍历找出左边最大子数组。然后以 mid+1为起点，向右遍历找出左边最大子数组。两个子数组拼接在一起，就是跨越中点的最大子数组。
时间复杂度：
分治策略求解最大子数组使用了递归求解的方法，因此我们需要建立一个递归式来描述上面算法的时间复杂度。
在这里，对问题进行简化，假设原问题是规模的2的幂，这样所有子问题的规模均为整数。
很明显，求解跨越中点的最大子数组的时间复杂度是 O(n)。
我们用 T(n) 表示时间复杂度，那么左右区间的时间复杂度为 2T(n/2)。
所以总的时间复杂度为 T(n)=2T(n/2)+O(n)。
此递归式与归并排序的递归式一样，求解递归式的时间复杂度可以采用《算法导论中》中文第三版的4.5节中提出的方法，可快速求解上面递归式的时间复杂度 T(n)=O(nlogn)。
空间复杂度： 递归会使用 O(logn) 的栈空间。
func maxSubArray(nums []int) int {
n := len(nums)
if n == 1 {
return nums[0]
}
mid := (n - 1) / 2
midMax := midMax(nums, mid)
leftMax := maxSubArray(nums[:mid+1])
rightMax := maxSubArray(nums[mid+1:])
max := math.Max(float64(rightMax), math.Max(float64(midMax), float64(leftMax)))
return int(max)
}
// 跨越中间点的最大子数组和。
func midMax(nums []int, m int) int {
maxl, maxr := math.MinInt, math.MinInt
var suml int
for i := m; i >= 0; i-- {
suml += nums[i]
if suml > maxl {
maxl = suml
}
}
var sumr int
for i := m + 1; i < len(nums); i++ {
sumr += nums[i]
if sumr > maxr {
maxr = sumr
}
}
return maxl + maxr
}4.3 贪心
对于一个包含负数的数组，从数组左边开始，依次累加元素和，当小于 0 时，从下一个元素重新开始累加并与前面最大子数组的和比较，记录最大者。
时间复杂度： O(n)。我们只需要遍历一遍数组即可求得答案。
空间复杂度： O(1)。我们只需要常数空间存放若干变量。
func maxSubArray(nums []int) int {
max := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i] + nums[i-1] > nums[i] {
nums[i] += nums[i-1]
}
if nums[i] > max {
max = nums[i]
}
}
return max
}参考文献
53. 最大子数组和 - LeetCode 算法导论中文版.原书第三版[M].P38-42