Return to Revisions

Looking at my code again, and looking at @rolfl's version of my code, I found a way to remove the outer loop, ending up with what looks pretty much the same as Kadane's algorithm that @JerryCoffin wrote. Personally I think this one's better though as this doesn't allow empty sub-arrays :) And that this actually returns the array and not the sum.

I think this code behaves in the exact same way my earlier code did, but without the outer-loop that was just clutter because of the break outer; and break; (a.k.a. continue outer;)

Also, as mentioned by @Nobody in the chat room, my original code had some lines that exceeded 80 characters (it had some 200+ lines!), avoiding writing too long lines is something I'll try to remember in the future.

Here's what I ended up with:

private static int[] scanArray(int[] array) {
    if (array == null || array.length == 0)
        throw new IllegalArgumentException("Array cannot be null and length must be > 0");

    int maxStartingIndex = 0;
    int maxEndingIndex = 0;
    int max = array[0];

    int currentSum = 0;
    int startLoop = 0;
    
    for (int index = 0; index < array.length; index++) {
        currentSum += array[index];

        // Check for a new record
        if (currentSum > max) {
            max = currentSum;
            maxStartingIndex = startLoop;
            maxEndingIndex = index;
        }

        // If we're below zero than there's no need to continue on this path.
        if (currentSum <= 0) {
            currentSum = 0;
            startLoop = index + 1;
        }
    }

    return Arrays.copyOfRange(array, maxStartingIndex, maxEndingIndex + 1);
}