53. 最大子数组和

[heyLiup]

https://leetcode.cn/problems/maximum-subarray/

贪心

var maxSubArray = function (nums) {
  let preSum = nums[0];  // 上一次的和，如果大于等于0，就加
  let max = nums[0];
  for (let i = 1; i < nums.length; i++) {
    let curSum = nums[i];
    if (preSum >= 0) {
      curSum = curSum + preSum;
    }
    preSum = curSum;

    max = Math.max(max, curSum);
  }
  return max;
};

动态规划

var maxSubArray = function (nums) {
  for (let i = 1; i < nums.length; i++) {
    let pre = nums[i - 1];
    if (pre >= 0) {
      nums[i] = nums[i] + pre;
    }
  }
  return Math.max(...nums);
};