最大子数组
在一个数字数组中找到具有最大和的连续子数组。
- 使用贪心算法来跟踪当前的
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]