Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Here is an attempt to extend the Kadane's Algorithm to return the sub array itself instead of the sum of maximum sub array. This must work irrespective of the original array having all positive or negative numbers.

public class MaxSubArray {

    public static void main(String[] args) {
        int array[] = {10, -9, 4, 5, 90, -19, 19}; // Max sum is 100
        //int array[] = {4, -3, 6}; // Max Sum is 7
        //int array[] = {-1, -2, -3}; // Max Sum is -1
        //int array[] = {1, -2, -3}; // Max Sum is 1
        //int array[] = {-4, -3, -6}; // Max Sum is -3
        //int array[] = {-6, 0, 5}; // Max Sum is 5
        //int array[] = {0, 0, 0}; // Max Sum is 0
        int[] maxSubArray = getMaxSubArray(array);
        System.out.println(Arrays.toString(maxSubArray));
    }

    // Kadane's Alorithm Variant (Start Index and End Index of Sub Array even for all negative numbers)
    private static int[] getMaxSubArray(int[] array) {
        if (array == null || array.length == 0) {
            return array;
        } else {
            int startIndex = 0, endIndex = 0;
            int maxSoFar = array[0], maxEndingHere = array[0];
            for (int i = 1; i < array.length; i++) {
                if(maxSoFar < array[i] && array[i] >= maxEndingHere + array[i]) {
                    maxEndingHere = array[i];
                    startIndex = i;
                    endIndex = i;
                } else {
                    maxEndingHere += array[i];
                }
                if(maxEndingHere > maxSoFar) {
                    maxSoFar = maxEndingHere;
                    endIndex = i;
                }
            }
            return Arrays.copyOfRange(array, startIndex, endIndex + 1);
        }
    }
}
share|improve this question

It will fail in the case 8, -19, 5, -4, 20. The startIndex and endIndex will not update until 20, but the start should be 5.

share|improve this answer

Bug

The first condition maxSoFar < array[i] is wrong and should be removed. Otherwise a sequence such as 5 -10 6 will not find 6 as the max sum.

Complicated expression

The other condition:

        if (array[i] >= maxEndingHere + array[i]) {

is overly complicated. If you subtract array[i] from both sides, you can simplify to:

          if (maxEndingHere <= 0) {
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.