53. Maximum Subarray

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

1. 动态规划

1.1 状态转移方程

假设$f(i)$表示以第i个数结尾的最大连续子数组和, 对于当前数字i:

• 若选择和前一个连续数组组成新数组则 $f(i) = f(i-1) + A[i]$
• 若选择单独成为数组则 $f(i)=nums[i]$

那么则有: $f(i)=max\{f(i-1)+A[i],A[i]\}, i > 0$

当i=0时, $f(0)$就为$A[0]$.

那么有状态转移方程:

$f(i)=\begin{cases} A[0], &i=0 \\ max\{f(i-1)+A[i], A[i]\}, & i>0 \end{cases}$

对于数组A[0, n-1], 最大连续子数组和为$max_{0,1,...,n-1}f(i)$

迭代+一维数组

func maxSubArray(nums []int) int {
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    maxSum := dp[0]

    for i := 1; i < len(nums); i++ {
        dp[i] = max(dp[i-1]+nums[i], nums[i])
        maxSum = max(maxSum, dp[i])
    }

    return maxSum
}

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

迭代+单变量

因为计算dp[i]只和dp[i-1]有关, 那么只需单个变量即可.

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

    return maxSum
}

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

Reference

1. https://leetcode.cn/problems/maximum-subarray/solutions/228009/zui-da-zi-xu-he-by-leetcode-solution/