题解 | #子数组的最大累加和问题#

53. 最大子序和
    给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出：6
    解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

//常规动规，时间On，空间On
func maxSubArray(nums []int) int {
    if len(nums) < 1 {
        return 0
    }

    n := len(nums)
       res := nums[0]

    dp := make([]int, n+1)        //当前连续数组的最大和
    dp[0] = nums[0]                //如果 dp[i-1] < 0，那么 dp[i] 其实就是 nums[i] 的值

    for i := 1; i < n; i++ {
        dp[i] = max(dp[i-1]+nums[i], nums[i])
        res= max(dp[i], res)
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

//滚动数组,空间优化为O1，类似前缀和的思路
func maxSubArray(nums []int) int {
    res:= nums[0]

    for i := 1; i< len(nums); i++ {
        if nums[i-1] > 0 {
            nums[i] += nums[i-1]
        }
        if nums[i] > res {
            res = nums[i]
        }
    }
    return res
}