使用 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
热门推荐
1 如何训练狗狗不叫
2 训练狗狗不叫
3 训练狗狗随行
4 怎么训练狗狗不叫
7 训练比熊狗狗教程
10 上海狗狗训练
11 怎么训练狗狗上厕所
12 训练狗狗趴下
13 狗狗服从训练
14 训练狗狗拒食
15 训练狗狗笑
16 训练狗狗大便
17 训练狗狗立
18 训练狗狗捡东西