53. 最大子序和

链接：https://leetcode-cn.com/problems/maximum-subarray/

执行用时：4 ms, 在所有 C++ 提交中击败了93.72%的用户
内存消耗：12.9 MB, 在所有 C++ 提交中击败了36.39%的用户

贪心算法

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

JavaScript:

var maxSubArray = function(nums) {
    let sum = nums[0];
    let thisSum = 0;
    for (let item of nums) {
        if (thisSum < 0) {
            thisSum = 0;
        }
        thisSum += item;
        sum = Math.max(sum, thisSum);
    }
    return sum;
}
========2==========
var maxSubArray = function(nums) {
    let pre = 0, maxAns = nums[0];
    nums.forEach((x) => {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    });
    return maxAns;

};

动态规划

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //res的初值也可设置为最小值
        //nums[0]可能是最小值且为负数
        int pre = 0, res = nums[0]; 
        for (auto num: nums) {
            pre = max(pre + num, num);
            res = max(pre, res);
        }
        return res;
    }
};

执行用时：1 ms, 在所有 Java 提交中击败了100.00% 的用户
内存消耗：48.7 MB, 在所有 Java 提交中击败了21.41% 的用户

java

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = nums[0], curSum = 0;
        for(int i: nums) {
            if(curSum < 0) {
                curSum = 0;
            } 
            curSum += i;
            sum = Math.max(sum, curSum);
        }
        return sum;
    }
}