最简单粗暴的算法：
func maxSubArray(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
max := nums[0]
for i := 0; i < len(nums); i++ {
tmp := 0
for j := i; j < len(nums); j++ {
tmp += nums[j]
if tmp > max {
max = tmp
}
}
}
return max
}看了一下官方的解，用动态规划和分治算法来做的。。。这两个东西都没学过，太难了
动态规划解法
func maxSubArray(nums []int) int {
max := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i]+nums[i-1] > nums[i] {
nums[i] += nums[i-1]
}
if nums[i] > max {
max = nums[i]
}
}
return max
}这个动态规划非常的巧妙，本质思想就是如果前一位+这一位大于这一位，那么这一位就加上前一位，然后后面依次比较。官方的解答如下
分治算法
这个算法是真的难，涉及到了线段树的概念
func maxSubArray(nums []int) int {
return get(nums, 0, len(nums) - 1).mSum;
}
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 max(x, y int) int {
if x > y {
return x
}
return y
}
type Status struct {
lSum, rSum, mSum, iSum int
}
