最大子数组

在一个数字数组中找到具有最大和的连续子数组。

  • 使用贪心算法来跟踪当前的sum和当前的最大值maxSum。将maxSum设置为-Infinity,以确保如果所有值都是负数,则返回最高的负值。
  • 定义变量来跟踪最大起始索引sMax、最大结束索引eMax和当前起始索引s
  • 使用Array.prototype.forEach()来迭代值并将当前值添加到sum中。
  • 如果当前的sum大于maxSum,则更新索引值和maxSum
  • 如果sum小于0,则将其重置为0,并将s的值更新为下一个索引。
  • 使用Array.prototype.slice()返回由索引变量指示的子数组。
const maxSubarray = (...arr) => {
  let maxSum = -Infinity,
    sum = 0;
  let sMax = 0,
    eMax = arr.length - 1,
    s = 0;

  arr.forEach((n, i) => {
    sum += n;
    if (maxSum < sum) {
      maxSum = sum;
      sMax = s;
      eMax = i;
    }

    if (sum < 0) {
      sum = 0;
      s = i + 1;
    }
  });

  return arr.slice(sMax, eMax + 1);
};


maxSubarray(-2, 1, -3, 4, -1, 2, 1, -5, 4); // [4, -1, 2, 1]