2
\$\begingroup\$

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);
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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) {
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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