使用 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