kadane algorithm in java

Question

I have the following implementation of Kadane's algorithm in java. It is basically to find the maximum sum of contiguous subarray.

String[] numbers = string.split(",");
                int max_so_far = 0;
                int max_ending_here = 0;
                for (int i = 0; i < numbers.length-1;i++){
                     max_ending_here = max_ending_here + Integer.parseInt(numbers[i]);
                     if (max_ending_here < 0)
                         max_ending_here = 0;
                     if (max_so_far < max_ending_here)
                          max_so_far = max_ending_here;
                }
                System.out.println(max_so_far);

However this doesn't work if there is a combination of a negative and positive number in an array, for example the following:

2,3,-2,-1,10

Which should return a 12 as a maximum. As of now it returns 5

Solution 1

You algorithm implementation looks ok, but your loop conditional i < numbers.length-1 does not: it stops just 1 short of the end of the array. i < numbers.length should do it :-)

Solution 2

this works for me:

    String string = "2,3,-2,-1,10";
    String[] numbers = string.split(",");
    int max_so_far = 0;
    int max_ending_here = 0;
    for (String num : numbers) {
        int x = Integer.parseInt(num);
        max_ending_here = Math.max(0, max_ending_here + x);
        max_so_far = Math.max(max_so_far, max_ending_here);
    }
    System.out.println(max_so_far);

Solution 3

Regarding the above answer by Michał Šrajer:

Line #7: max_ending_here = Math.max(0, max_ending_here + x);

should be:

max_ending_here = Math.max(x, max_ending_here + x);

...according to the Kadane algorithm as defined here

Comments

[Oliver Charlesworth]

What is the question here? Have you tried debugging this?

[luketorjussen]

what value does it give at the moment?

[Michał Šrajer]

This is why for each loop is so great. You avoid such gotchas.

[Kemat Rochi]

+1 for pointing this out. It is important to note that if all the numbers in the input array are -ve then the accepted solution will not give the right answer.

[marathon]

This fails if all the elements in the array are negative. you probably need to initialize your variables to Integer.MIN_VALUE or to the first element of the array.