給定一個(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è)半部分。前兩種情況遞歸求解。第三種情況的最大和可以通過求出前半部分的最大和（包含前半部分的最后一個(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
}