我在 javascript 中实现了 Kadane 的最大子数组问题,但似乎即使存在更高的数字,我最终总是在控制台中得到 0(我知道它做了它正在做的事情,因为从 0 - size
哪里size = subarray size
的 for 循环)。
-
那么如何正确实现算法呢?
-
它是否也适用于所有正整数数组?
杰斯宾
http://jsbin.com/ajivan/edit#javascript,live
你传递 n=3 作为参数,而你的数组的长度为 6。我更改了您的算法以使用length
:
function SubSequence(a){
var now = 0,prev =0;
for(var i = 0;i < a.length;i++){
prev = Math.max(0,prev + a[i]);
now = Math.max(prev,now);
}
return now;
}
console.log(SubSequence([-1,-2,-3,4,6,7]));
它给出了 17。
它是否也适用于所有正整数数组?
是的,然后它将给出数组中所有元素的总和。
如果需要长度为 3 的最大子序列,请使用
function SubSequence(a,n){
var now = 0;
for(var i = 0; i < n; i++) {
now += a[i];
}
var best = now;
for(var i = n;i < a.length;i++) {
now += a[i] - a[i-n];
best = Math.max(now,best);
}
return best;
}
console.log(SubSequence([-1,-2,-3,4,6,7,1,4],3));
最好的是4+6+7,而4+6+7+1+4是不允许的。
在计算机科学中,最大子数组问题是在具有最大和的一维数字数组(包含至少一个正数)中找到连续子数组的任务。
Kadane算法是一种找到上述问题解决方案的方法。
Kadane 算法的简单想法是寻找数组的所有正连续段(假设 max_ending_here)。并跟踪所有正段(假设max_so_far)之间的最大总和连续段。每次我们得到正和时,都会将其与max_so_far进行比较,如果大于 max_so_far,则更新max_so_far。
算法不适用于所有负数。如果所有数字均为负数,则它仅返回 0。为了解决这个问题,我们可以在实际实现之前添加一个额外的阶段。该阶段将查看是否所有数字都是负数,如果是,它将返回其中的最大值(或绝对值方面的最小值)
您发布的是在数组中的所有数字均为负数的情况下的实现。它不是指实际的算法,而只是一个额外的阶段。一维数组的卡达内算法:
this is the general algorithm.
Initialize:
max_so_far = 0
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far
希望这个解释对你有帮助。
这个问题已经很晚了,但是,以防万一它对任何人有帮助,我对这个问题的尝试包括数组的所有元素都是负数的情况。
let allPositives = arr => arr.every(n => n > 0)
let allNegatives = arr => arr.every(n => n < 0)
let sum = arr => arr.reduce((curr_max, max_so_far) => curr_max + max_so_far, 0)
var getMaxArrNumber = function (arr) {
return Math.max.apply(null, arr);
}
var maxSequence = function(arr){
if(arr.length === 0 ) return 0;
if(allNegatives(arr)) return getMaxArrNumber(arr);
if(allPositives(arr)) return sum(arr);
var curr_max = 0, max_so_far = 0;
for(var i = 0; i < arr.length; i++){
curr_max = Math.max(0, curr_max + arr[i]);
max_so_far = Math.max(curr_max, max_so_far);
}
return max_so_far;
}