给你一个整数数组 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
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
解答：
func maxSubArray(nums []int) int {
l := len(nums)
maxSum := nums[0]
for i := 0; i < l; i++ {
sum := 0
for j := i; j < l; j++ {
sum += nums[j]
if sum > maxSum {
maxSum = sum
}
}
}
return maxSum
}超时了就很郁闷
官方解答：
1.动态规划
func maxSubArray(nums []int) int {
max := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i-1] > 0 {
nums[i] += nums[i-1]
}
if nums[i] > max {
max = nums[i]
}
}
return max
}2.分治
type Status struct {
lSum, rSum, mSum, iSum int
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
func pushUp(l, r Status) Status {
iSum := l.iSum + r.iSum
lSum := max(l.lSum, l.iSum+r.lSum)
rSum := max(r.rSum, r.iSum+l.rSum)
mSum := max(max(l.mSum, r.mSum), l.rSum+r.lSum)
return Status{lSum, rSum, mSum, iSum}
}
func get(nums []int, l, r int) Status {
if l == r {
return Status{nums[l], nums[l], nums[l], nums[l]}
}
m := (l + r) >> 1
lSub := get(nums, l, m)
rSub := get(nums, m+1, r)
return pushUp(lSub, rSub)
}
func maxSubArray(nums []int) int {
return get(nums, 0, len(nums)-1).mSum
}