Kadane的Max Sub Array算法是否适用于所有正整数数组？ [英] Does Kadane's Max Sub Array algorithm work on all positive integer 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。

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

Does it also work for all positive integer array?

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

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算法是否适用于所有正整数数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！