kadane algorithm in java

问题:

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

回答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 :-)

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

回答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

回答4:

Too late, but if someone needs it in the future.

public static void kadaneAlgo(int[][] array)
    for(int i = 1; i < array.length; i++){
            int max_value_index_i = numberOrSum(array[i], past);
            if(max_value_index_i > sum){
                sum = max_value_index_i;
            }
            past = max_value_index_i;

        }
        System.out.println("Max sum from a contiguous sub array is : " + sum);
    }

    public static int numberOrSum(int number, int past){
        return Math.max(number, number+past);
    }