Kadane的Max Sub Array算法是否适用于所有正整数数组？

问题描述

我在javascript中实现了Kadane的Max Sub数组问题，但即使存在更高的数字，我似乎总是总是在控制台中得到0（我理解它之所以会这样做是因为的for循环0-size ，其中 size =子数组大小）。

I Implemented the Kadane's Max Sub array problem in javascript but seems i end up always getting 0 in the console even though there exists higher numbers( I understand that it does what it's doing because of for loop from 0 - size where size = subarray size).

• 那么我如何正确实现算法？

• So how do i implement the algorithm correctly?

它也适用于所有正整数数组吗？

Does it also work for all positive integer array?

http://jsbin.com/ajivan/edit#javascript,live

推荐答案

当数组长度为6时，您将n = 3作为参数传递。我将算法更改为使用 length ：

You're passing n=3 as an argument while your array has length 6. I changed your algorithm to use 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。

是的，它将给出所有元素的总和

Yes, it will then give sum of all elements in the array.

如果想要最大长度为3的子序列，请使用

If you want maximal subsequence of length 3, use

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不是允许。

the best is 4+6+7, while 4+6+7+1+4 is not allowed.

这篇关于Kadane的Max Sub Array算法是否适用于所有正整数数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！