給定一個(gè)整數(shù)數(shù)組 nums 车摄，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）亡脑，返回其最大和昂芜。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大情妖，為 6。
思路：遞歸實(shí)現(xiàn)逮矛，時(shí)間復(fù)雜度為O(nlogn)。
分治的思想：最大子序列和可能出現(xiàn)在三處转砖⌒攵Γ或者整個(gè)出現(xiàn)在輸入數(shù)據(jù)的左半部，或者整個(gè)出現(xiàn)右半部府蔗，或者跨越輸入數(shù)據(jù)的中部從而占據(jù)左右兩個(gè)半部分晋控。前兩種情況遞歸求解。第三種情況的最大和可以通過(guò)求出前半部分的最大和（包含前半部分的最后一個(gè)元素）以及后半部分的最大和（包含后半部分的第一個(gè)元素)而得到姓赤，然后將這兩個(gè)和加在一起赡译，求出三個(gè)值的最大值。
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
}
