刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/maximum-subarray/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你一个整数数组 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

思路

最直接的贪心算法就不说了。

动态规划也可，不过需要注意，dp定义应该是以i结尾的最大子数组和，而前i个元素的最大子数组和这个定义是不可的，因为题目需要找的是连续的子数组，不以i结尾的子数组是无法连续的，没有意义。

这里主要提下学习到的一个分治法。
分而治之，那就是先有一个左右划分，然后列举情况，这里会有三种，

• 最大子数组和在左半边
• 最大子数组和在右半边
• 最大子数组和包含了中间值
  分完三种情况，就是看每种情况的退出条件
• 在两边的情况分治下去那就是直至单一元素则退出，返回上层参与比较
• 横跨中间值的，则是在中间元素已经有了的情况下，向左右延伸，得出包含中间值的最大子数组和，返回上层参与比较

大体就是这样了，详情可以参考这篇优秀题解：分治法题解

代码

func maxSubArray(nums []int) int {
	if len(nums) <= 0 {
		return 0
	}
	return maxSubArraySum(nums, 0, len(nums)-1)
}

func maxSubArraySum(nums []int, left, right int) int {
	if left == right {
		return nums[left]
	}
	//mid := (left + right) / 2
	mid := left + (right-left)/2
	return max(max(maxSubArraySum(nums, left, mid), maxSubArraySum(nums, mid+1, right)), maxCrossMidSubArraySum(nums, left, right, mid))
}

func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func maxCrossMidSubArraySum(nums []int, left, right, mid int) int {
	// mid一定包含，分别求往左、往右能拿到最大的和，相加返回
	leftSum := math.MinInt
	tempSum := 0
	for i := mid; i >= left; i-- {
		tempSum += nums[i]
		if tempSum > leftSum {
			leftSum = tempSum
		}
	}

	rightSum := math.MinInt
	tempSum = 0
	for i := mid + 1; i <= right; i++ {
		tempSum += nums[i]
		if tempSum > rightSum {
			rightSum = tempSum
		}
	}
	return leftSum + rightSum
}