Does Kadane's Max Sub Array algorithm work on all positive integer array?

algorithm, arrays, javascript, kadanes-algorithm

Solution

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]));

and it gives 17.

Does it also work for all positive integer array?

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

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));

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

Problem

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? JsBin http://jsbin.com/ajivan/edit#javascript,live

Original source