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

Question

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

Answer 1

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.

Answer 2

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum.

Kadane's algorithm is a method to find the solution of above problem.

Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (lets say max_ending_here). And keep track of maximum sum contiguous segment among all positive segments (lets say max_so_far). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far.

Algorithm doesn't work for all negative numbers. It simply returns 0 if all numbers are negative. For handling this we can add an extra phase before actual implementation. The phase will look if all numbers are negative, if they are it will return maximum of them (or smallest in terms of absolute value)

What you have posted is the implementation in the case when all the numbers in the array are negative.It does not refer to the actual algorithm but just an extra phase. The Kadane's algorithm for 1 D array :

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

hope this explanation will be helpful for you.

Answer 3

Very late ans here on this question, however, just in case it helps anybody, my attempt at the problem including the case when all elements of the array are negatives.

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