本文首发于WXGZH：小夕学算法

小夕：采取贪心策略，只要当前子段的和最大，就记录到maxSum中，如果sum的结果小于0，必须将sum = 0，然后重新开始计算新的子段和，因为加上负数只会更小。我用题目中的例子画一下图说明一下，更清晰一些。

贪心代码

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int maxSum = nums[0];
        for (int i = 0;i < nums.length; i++) {
            sum += nums[i];
            if (sum > maxSum) maxSum = sum;
            if (sum < 0) sum = 0;
        }
        return maxSum;
    }
}

C++

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN, sum = 0;
        for(int n : nums)
        {
            sum += n;
            if(sum > res)   res = sum;
            if(sum < 0)     sum = 0;
        }
        return res;
    }
};

Python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return None
        s_max,s_sum = nums[0],0
        for i in range(len(nums)):
            s_sum=s_sum+nums[i]
            if s_sum>s_max:
                s_max=s_sum
            if s_sum<0:
                s_sum=0
        return s_max

JS

// ac地址：https://leetcode-cn.com/problems/maximum-subarray/
// 原文地址：https://xxoo521.com/2020-03-09-max-sub-sum/
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let maxSum = (sum = nums[0]);
    for (let i = 1; i < nums.length; ++i) {
        sum = Math.max(nums[i], sum + nums[i]);
        maxSum = Math.max(maxSum, sum);
    }
    return maxSum;
};

贪心图解

贪心动画

gif

动态规划思路

• 转移方程：
  • 当 dp[i-1] > 0 ，dp[i] = dp[i-1] + nums[i]
  • 当 dp[i-1] <= 0 , dp[i] = nums[i]
    因为当dp[i-1] 是负数的话，加上 nums[i] 必然小于nums[i]本身，所以当 dp[i-1] <= 0 , dp[i] = nums[i]

动态规划图解

动态规划动画

动态规划动画.gif

动态规划代码

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        int max = nums[0];
        dp[0] = nums[0];
        for(int i = 1; i < nums.length; i++) {
            if (dp[i - 1] < 0) {
                dp[i] = nums[i];   
            } else {
                dp[i] = dp[i-1] + nums[i];
            }
            if (dp[i] > max) max = dp[i];
        }
        return max;
    }
}

C++

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = nums[0];
        for(int i = 1; i < nums.size(); ++i)    
        {
            if(nums[i-1] > 0)   nums[i] = nums[i-1] + nums[i];
            res = max(res,nums[i]);
        }
        return res;
    }
};

JS

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    // 获取数组长度
    const numsLength = nums.length
    if(numsLength === 1){
        return nums[0]
    }
    let max = nums[0]
    // 存放 dp 的数据
    let dpi = nums[0]
    // 实现循环迭代
    for(let i = 1; i < numsLength; i ++){
        // dp 计算规则为如果 上次 dp > 0 让上次 dp 参与计算，否则丢弃
        dpi = dpi > 0 ? dpi + nums[i] : nums[i]
        // 在上次的最大值和计算好的 dp 中取最大值
        max = max > dpi ? max : dpi
    }
    return max
};

Python

class Solution(object):
    def maxSubArray(self, array):
        max = array[0]
        dp = [0] * (len(array) + 1)
        dp[0] = array[0]
        for i in range(1, len(array)):
            if dp[i-1] < 0:
                dp[i] = array[i]
            else:
                dp[i] = array[i] + dp[i-1]
            if dp[i] > max:
                max = dp[i]
        return max