剑指Offer 42. 连续子数组的最大和-526互联

题目描述：

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

解法思路：

本题为经典的动态规划题目：
技巧：

可以使用一个变量求解，变量s表示以前一个数为结尾的所有子数组的最大和，从左向右依次遍历数组nums
如果 s > 0，说明前面的最大子数组和大于0 ，则加上现在的数（因为加上正数，肯定是对求最大子数组有利的）
如果 s <= 0 ,说明前面的最大子数组之和小于0 ，则不进行操作（因为加上一个负数，会变得更小，加上0 ，没意义）
此时比较当前的最大子数组之和与结果res，取两者的最大值
最后返回res

代码：

func maxSubArray(nums []int) int {
    var res int
    if len(nums) == 0 {  //判空
        return res
    }
    res = nums[0] //初始时，res = 数组第一个元素值
    s := nums[0]
    for i:=1;i<len(nums);i++{
        if s > 0 { // 如果大于0，相加，更新s
            s += nums[i]
        }else{  // 否则，s 等于当前值（也就是表示以当前值为结尾的子数组，和最大是s）
            s = nums[i]
        }
        if s > res{  //更新结果res
            res = s
        }
    }
    return res
    
}

优化
可以直接在nums数组上进行操作，省去变量s

func maxSubArray(nums []int) int {
    var res int
    if len(nums) == 0 {
        return res
    }
    res = nums[0] 
    for i,_ := range nums{
        if i > 0 && nums[i-1] > 0{
            nums[i] += nums[i-1] 
        }
        if nums[i] > res{
            res = nums[i]
        }

    }
    return res

}