使用 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
热门推荐
6 保研的祝福语简短
10 年轻20岁祝福语简短
11 朋友结婚祝福语信息简短
12 女孩婚礼贺卡祝福语简短
13 30段点歌简短祝福语
14 虎年春节祝福语图文简短
15 写给后妈祝福语大全简短
16 简短回复生日祝福语
17 校长送毕业祝福语简短
18 毕业立体贺卡祝福语简短