最大子数组和

53. 最大子数组和

• 暴力

204 / 209 个通过测试用例

func maxSubArray(nums []int) int {
    n := len(nums)
    ans := nums[0]
    for i := 0; i < n; i++ {
        sum := 0
        for j := i; j < n; j++ {
            sum += nums[j]
            ans = max(ans, sum)
        }
    }
    return ans
}

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

• 动态规划

dp[i]表示0~i范围内，子数组的末尾下标为i的子数组中，和最大的

func maxSubArray(nums []int) int {
    n := len(nums)
    ans := nums[0]
    dp := make([]int, n+1)
    for i := 1; i <= n; i ++ {
        dp[i] = max(nums[i-1], nums[i-1] + dp[i-1])
        ans = max(ans, dp[i])
    }
    return ans
}

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