给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
方法一：动态规划
- 时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
- 空间复杂度：O(1)，只需要常数空间。
维护两个变量，一个前指针的变量，一个是最大和的变量，若前一个元素大于0，则加到当前元素上
- 每循环一次的时候，将当前指针位置的值 和 current 相加后，和当前指针的值做对比，取两者最大的
- 其实current变量累加起来后就相当于一个连续子序累加的和，如果一直都是最大的话，就用上面的数组举例子
i: 0 1 2 3 4 5 6 7 8
nums: [-2 1 -3 4 -1 2 1 -5 4]
current: -2 1 -2 4 3 5 6 1 5 比较公式：max(current + nums[i], nums[i])
例如nums[1]和nums[2]这两个地方，max(1 + (-3), -3) 相当于 max(-2,-3) 结果为-2，所以 current变成了-2
max: -2 1 1 4 4 5 6 6 6
直接获取current里面出现过的最大值，就是答案了，也就是6
func maxSubArray(nums []int) int {
//定义一个指向上一个值的指针
current := nums[0]
//定义 一个最大和
max := nums[0]
for i:=1;i<len(nums);i++ {
//将当前指针位置的值和current相加后，和当前节点做对比，取两者最大的
current = Max(current + nums[i], nums[i])
max = Max(max, current )
}
return max
}
func Max(a,b int) int {
if a > b {
return a
}
return b
}
动态规划优化 上面的方法还能再优化一下，只维护一个max值就好了，current直接用上一个指针来nums[i-1]存储就好了
func maxSubArray(nums []int) int {
//定义 一个最大和
max := nums[0]
for i:=1;i<len(nums);i++ {
//将当前指针位置的值和前指针相加后，和当前节点做对比，取两者最大的
nums[i] = Max(nums[i-1] + nums[i], nums[i])
max = Max(max, nums[i]
}
return max
}
func Max(a, b int) int {
if a > b {
return a
}
return b
}
方法二：
贪心算法，从数组开头累加sum,sum小于零直接重置为0
- 时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
- 空间复杂度：O(1)，只需要常数空间。
nums [-2 1 -3 4 -1 2 1 -5 4]
sum(初始值0): -2 1 -2 4 3 5 6 1 5
max(初始值math.MinInt64): -2 1 1 4 4 5 6 6 6
=====================================================================
func maxSubArray(nums []int) int {
sum := 0
max:= math.MinInt64
for i:=0;i<len(nums);i++ {
sum += nums[i]
max= Max(res,sum)
if sum < 0 {
sum = 0
}
}
return max
}
func Max(a,b int) int {
if a > b {
return a
}
return b
}
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
方法三：分治法,将数组分为3个部分处理
- 分别就是三种情况，要么最大子序列在左边，要么在右边，要么就是跨过左边和右边
- 比较的时候，就把左序列和右序列 和 （左 + 右）3个一起对比取最大值
复杂度分析
- 时间复杂度：O(Nlog N)，分治法采用二分法，时间是log n，因为每次都需要计算横跨左右序列的和，时间复杂度为N，所以总时间复杂度为Nlog N。
- 空间复杂度：递归会使用 O(log N) 的栈空间，故渐进空间复杂度为 O(\log n)O(logn)。
nums[] int -2 1 -3 4 -1 2 1 -5 4
# l=4 r=4 m=6 max=6
[-2 1 -3 4] [-1 2 1 -5 4]
# l=1 r=4 m=2 max=4 # l=2 r=4 m=3 max=4
[-2 1] [-3 4] [-1 2] [1 -5 4]
[-2] [1] [-3] [4] [-1] [2] [1] [-5 4]
# l=1 r=4 m=0 max=4
[-5] [4]
//分治法，用二分法分别在两边找出最大的连续子序，数据结构为线段树
func maxSubArray(nums []int) int {
return help(nums, 0, len(nums) - 1);
}
func help(nums [] int,l, r int) int {
//当左指针等于右指针的时候，就是已经递归到最后面了，只有一个值
if (l == r) {
return nums[l]
}
m := (l + r) >> 1
leftSum := help(nums, l, m)
rightSum := help(nums, m + 1, r)
midSum := getCrossMax(nums, l, m, r)
return max(max(leftSum,rightSum),midSum)
}
//获取横跨左右序列的最大连续序列
func getCrossMax(nums []int,left,mid,right int) int {
//获取左序列最大连续子序列的和
leftSum := math.MinInt64
sum := 0
for i := mid; i >= left; i-- {
//贪心算法获取最大和
sum += nums[i]
leftSum = max(leftSum,sum)
}
//获取右序列最大连续子序列的和
rightSum := math.MinInt64
sum = 0
for i := mid + 1; i <= right; i++ {
//贪心算法获取最大和
sum += nums[i]
rightSum = max(rightSum,sum)
}
return (leftSum + rightSum)
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
