使用 Kadane 算法在 JavaScript 中找到子数组的最大和
问题
我们需要编写一个JavaScript函数，它接受一个整数数组（正数和负数）arr作为第一个也是唯一的参数。
我们的函数应该在线性时间内返回任何子数组的最大和
任意索引i处的local_maximum是arr[i]的最大值以及索引i-1处arr[i]和local_maximum的总和。
这就是我们要在线性时间内找到数组中最大子数组和的方法。
例如，如果函数的输入是-
输入
const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
输出
const output = 6;
输出说明
因为具有最大和的子数组是-
[4, -1, 2, 1]
示例
以下是代码-
const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const maxSequence = (arr = []) => {
let currentSum = 0
let maxSum = 0
for (let elem of arr) {
const nextSum = currentSum + elem
maxSum = Math.max(maxSum, nextSum)
currentSum = Math.max(nextSum, 0)
}
return maxSum
};
console.log(maxSequence(arr));输出结果6
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短