53. 最大子数组和

53. 最大子数组和

• 难度: medium
• 原始链接: https://leetcode.cn/problems/maximum-subarray
• 标签: 动态规划, 分治法

解法一: 动态规划

go

func maxSubArray(nums []int) int {
    ans := nums[0]
    pre := nums[0]
    for _, num := range nums[1:] {
        pre = max(pre + num, num)
        ans = max(ans, pre)
    }
    return ans
}

func max(num1, num2 int) int {
    if num1 >= num2 {
        return num1
    }
    return num2
}

解法二: 分治法

go

func maxSubArray(nums []int) int {
    return dfs(nums, 0, len(nums) - 1)
}

func dfs(nums []int, left int, right int) int {
    if left == right {
        return nums[left]
    }
    mid := ((right - left) >> 1) + left
    leftSum := dfs(nums, left, mid)
    rightSum := dfs(nums, mid + 1, right)
    midSum := calcMidSubArray(nums, left, right, mid)
    return max(leftSum, max(rightSum, midSum))
}

func calcMidSubArray(nums []int, left, right, mid int) int {
    leftSum := -1000000000
    sum := 0
    for i := mid; i >= left; i-- {
        sum += nums[i]
        if sum > leftSum {
            leftSum = sum
        }
    }

    rightSum := -1000000000
    sum = 0
    for i := mid + 1; i <= right; i++ {
        sum += nums[i]
        if sum > rightSum {
            rightSum = sum
        }
    }

    return leftSum + rightSum
}

func max(num1, num2 int) int {
    if num1 >= num2 {
        return num1
    }
    return num2
}