53. 最大子序和 👌

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 {
    n := len(nums)
    res:= nums[0]

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

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

    n := len(nums)
    dp := make([]int, n)            //当前连续数组的最大和
    dp[0] = nums[0]

    for i := 1; i < n; i++ {
        if dp[i-1] + nums[i] > nums[i] {
            dp[i] = dp[i-1] + nums[i]
        } else {
            dp[i] = nums[i]            //如果 dp[i-1] < 0，那么 dp[i] 其实就是 nums[i] 的值
        }
    }

    res := dp[0]
    for _, v := range dp {
        if v > res {
            res = v
        }
    }

    return res
}