给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路：递归实现，时间复杂度为O(nlogn)。
分治的思想：最大子序列和可能出现在三处。或者整个出现在输入数据的左半部，或者整个出现右半部，或者跨越输入数据的中部从而占据左右两个半部分。前两种情况递归求解。第三种情况的最大和可以通过求出前半部分的最大和（包含前半部分的最后一个元素）以及后半部分的最大和（包含后半部分的第一个元素)而得到，然后将这两个和加在一起，求出三个值的最大值。
func maxSubArray(nums []int) int {
return divide(nums, 0, len(nums)-1)
}
func divide(nums []int, left, right int) int {
if left == right {
return nums[left]
}
mind := (left + right) / 2
maxLeftSum := divide(nums, left, mind)
maxRightSum := divide(nums, mind+1, right)
var maxMindLeftSum, mindLeftSum int
for i := mind; i >= left; i-- {
mindLeftSum += nums[i]
if mindLeftSum > maxMindLeftSum {
maxMindLeftSum = mindLeftSum
}
}
var maxMindRightSum, mindRightSum int
for i := mind + 1; i <= right; i++ {
mindRightSum += nums[i]
if mindRightSum > maxMindRightSum {
maxMindRightSum = mindRightSum
}
}
var max int
if maxLeftSum > maxRightSum {
max = maxLeftSum
} else {
max = maxRightSum
}
if max < maxMindRightSum+maxMindLeftSum && maxMindRightSum+maxMindLeftSum != 0 {
max = maxMindRightSum + maxMindLeftSum
}
return max
}
