Finding the sub-array with the maximum sum - my approach

Question

This is the code I ended up with that implements the approach I described in a recent answer to another question about the same problem

The basic idea here is to not loop through more things than necessary.

I have also added a parameterized JUnit test.

I would like to know what you think of this code.

Any comments welcome.
Are there any edge-cases I'm missing? (I believe I've covered it all, many thanks to the folks in the 2nd Monitor for the discussion about the previous question).
I'm quite sure that it is possible to change the code to get rid of the inner for-loop entirely so that there will only be one for-loop. I have not completely investigated this though, but this code is still a massive improvement compared to the first version of my approach
How efficient is this code? Is it doing too much?
Expected complexity \$O(n)\$ (some indexes are currently iterated twice, but mostly it's just once)

My approach

@RunWith(Parameterized.class)
public class SubArrayMaximumSum {

    private int low;
    private int high;
    private int[] array;

    public SubArrayMaximumSum(int lowIndex, int highIndex, int[] array) {
        this.low = lowIndex;
        this.high = highIndex;
        this.array = array;
    }

    @Parameters
    public static List<Object[]> parameters() {
        List<Object[]> list = new ArrayList<>();
        list.add(new Object[]{ 3, 8, new int[]{-5, 1, -3, 7, -1, 2, 1, -4, 6}});
        list.add(new Object[]{ 3, 6, new int[]{-5, 1, -3, 7, -1, 2, 1, -6, 5}});
        list.add(new Object[]{ 1, 4, new int[]{-5, 6, -3, -2, 7, -5, 2, 1, -7, 6} });
        list.add(new Object[]{ 2, 2, new int[]{-5, -2, -1, -4, -7} });
        list.add(new Object[]{ 0, 8, new int[]{4, 1, 1, 4, -4, 10, -4, 10, 3, -3, -9, -8, 2, -6, -6, -5, -1, -7, 7, 8} });
        list.add(new Object[]{ 5, 11,new int[]{4, -5, -1, 0, -2, 20, -4, -3, -2, 8, -1, 10, -1, -1 } });
        return list;
    }

    @Test
    public void test() {
        assertArrayScan(low, high, array);
    }

    private static void assertArrayScan(int startIndex, int endIndex, int[] array) {
        System.out.println("Original : " + Arrays.toString(array));

        int[] expected = Arrays.copyOfRange(array, startIndex, endIndex + 1);
        System.out.println("Expecting: " + Arrays.toString(expected));

        int[] actual = scanArray(array);
        System.out.println("Actual   : " + Arrays.toString(actual));
        System.out.println("----------------------------------------");
        assertArrayEquals(expected, actual);
    }

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

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

        outer:
        for (int startLoop = 0; startLoop < array.length; startLoop++) {
            int value = array[startLoop];
            // To allow an array of all negatives, check if this value alone is more than the previous maximum.
            if (value > max) {
                max = value;
                maxStartingIndex = startLoop;
                maxEndingIndex = startLoop;
            }

            // If this value is below zero, there's no need in starting to loop here, it's better to start looping on a positive value.
            if (value < 0)
                continue;
            System.out.println();
            System.out.println(String.format("Starting looping on %d, max is %d for indexes %d -- %d", startLoop, max, maxStartingIndex, maxEndingIndex));

            int currentSum = value;
            for (int innerLoop = startLoop + 1; innerLoop < array.length; innerLoop++) {
                currentSum += array[innerLoop];

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

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

                System.out.println(String.format("CurrentSum %d, i %d, j %d, max is %d for index %d -- %d", currentSum, startLoop, innerLoop, max, maxStartingIndex, maxEndingIndex));

                // Check if we have reached the end of the array. If we have, then there's no need in continuing the outer iterations. We know the max already
                if (innerLoop == array.length - 1) {
                    break outer;
                }
            }
        }

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

}

rolfl · Accepted Answer · 2014-06-02 15:00:01Z

The code appears to be sane, and reasonable.

Logic Duplication

There are a couple of logic duplications. For example:

        // If this value is below zero, there's no need in starting to loop here,
        //   it's better to start looping on a positive value.
        if (value < 0)
            continue;

The value < 0 check is actually duplicated (if you adjust the code a bit) inside the inner loop with:

            currentSum += array[innerLoop];

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

Additionally, the condition inside the inner loop:

            // Check if we have reached the end of the array. If we have,
            // then there's no need in continuing the outer iterations. We
            // know the max already
            if (innerLoop == array.length - 1) {
                break outer;
            }

is part of the loop condition too:

for (int innerLoop = startLoop + 1; innerLoop < array.length; innerLoop++) {

Improvements

The test for currentSum < 0 would be better as currentSum <= 0

Did I see an un-braced 1-liner!!!!:

        if (value < 0)
            continue;

should be:

         if (value < 0) {
             continue;
         }

Performance

The println statements are great for debugging, but will kill any performance. With those removed, the question comes down to performance....

There are no autoboxings I can see, there's no new objects created in any of the loops.

With the duplicate conditions removed, the code has very few additional comparisons that naieve code would not already have.

All in all, it looks good. Now, to actually profile, and benchmark it.

I would benchmark with (this is your code, with redundant checks removed, a tweak of the break/continue logic, and no printlns....):

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

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

    int startLoop = 0;
    outer:
    while (startLoop < array.length) {
        int currentSum = 0;
        for (int innerLoop = startLoop; innerLoop < array.length; innerLoop++) {
            currentSum += array[innerLoop];

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

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

        }
        // we looped through to the end... there's no better solution.
        break outer;
    }

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

Jerry Coffin · Accepted Answer · 2014-06-02 20:01:16Z

The original question didn't specify quite enough to define the correct answer with absolute certainty. In particular, if all the inputs are negative, is one allowed to treat an empty subset as satisfying the requirement, and give a result of 0?

It's pretty easy to implement either way, but for the moment I'm going to assume that an empty sub-sequence allowed, so the result should never be less than 0.

In that case, it seems to fit Kadane's algorithm, which is linear. In pseudo-code, it looks something like this:

best-so-far = 0;
best-ending-here = 0;

for (item in collection)
    best-ending-here = max(0, best-ending-here + item);
    best-so-far = max(best-so-far, best-ending-here);
return best-ending-here

One possible translation of that into code (C++, not Java) looks like this:

template <class Coll>
typename Coll::value_type find_max(Coll const &c) { 
    typedef typename Coll::value_type T;
    T best_so_far{};
    T best_here  {};

    for (auto t : c) {
        best_here = std::max(0, best_here + t);
        best_so_far = std::max(best_here, best_so_far);
    }
    return best_so_far;
}

I rarely write Java, so I might get a few details wrong, but in Java this should look something like this (doing a version specifically for int at the moment):

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

    int best_so_far = 0;
    int best_here = 0;

    for (int i=0; i<array.length; i++) {
         best_here = Math.Max(0, best_here + array[i]);
         best_so_far = Math.Max(best_here, best_so_far);
    }
    return best_so_far;
}

A quick test of the C++ version shows that (compiled with gcc 4.8.1 with -O3, running on one core of a 3.7 GHz i7) this can process data at a rate of about a million ints per millisecond.

At least offhand, I believe the Java translation (with any necessary corrections) should run close to the same speed. It might be a tiny bit slower (or even a tiny bit faster) but I'd be pretty surprised to see any really significant differences. In particular, I'd expect both to be limited almost entirely by the bandwidth to main memory under most circumstances, rendering any differences in processing speed completely irrelevant under most circumstances (but the same is probably true of Simon's code in his question, so the big gain is in code simplicity, not speed).

As far as a code review goes: the biggest issue I see is that the complexity of the algorithm is difficult to analyze. In the end, it looks like it probably ends up fairly close to Kadane's algorithm, but it's expressed in a way that it initially looks like it's O(N²).

Other than that, the code I've given above is probably faster in actual fact as well. Ignoring the loop overhead, it should end up with something like one addition, two comparisons, and two assignments per iteration. I haven't gone through your code in enough detail to count up the operations, but at least at first glance it certainly looks like it's executing more in at least some iterations of the outer loop. Also, while I feel pretty comfortable ignoring the overhead of the outer loop (since it seems pretty much unavoidable) the overhead of your inner loop isn't so easy to ignore (since I think it is avoidable).

2 revs, 2 users 99% · Accepted Answer · 2020-06-10 13:24:26Z

Performance Benchmarks

In the interest of performance benchmarking, I put three versions of the code through some benchmarks. The three version are:

My answer to the original quesiton
Simon's answer with the code in this question.
My suggested changes to Simon's answer here.

The results are .... interesting.

Array Sum Rolfl     => [-1, 1, 11, 9, 8, -1, 25, 28, 45769, 447857, 50645434] (hot 50.95695ms - cold 50.789ms (total 56082.850ms))
Array Sum SAF       => [-1, 1, 11, 9, 8, -1, 25, 28, 45769, 447857, 50645434] (hot 0.02366ms - cold 0.038ms (total 48.741ms))
Array Sum SAF Rolfl => [-1, 1, 11, 9, 8, -1, 25, 28, 45769, 447857, 50645434] (hot 0.01728ms - cold 0.029ms (total 22.938ms))

Let's ignore the first numbers for a bit (they are the 'results' of the tests). What it shows is that all three tests got the same results... so they are 'equivalent'). Let's focus on the timings:

Array Sum Rolfl     => (hot 50.95695ms - cold 50.789ms (total 56082.850ms))
Array Sum SAF       => (hot 0.02366ms - cold 0.038ms (total 48.741ms))
Array Sum SAF Rolfl => (hot 0.01728ms - cold 0.029ms (total 22.938ms))

Simon's answer is 250 times faster than mine. My suggested changes make Simon's code faster by a third.

Simon's answer, by itself, is a huge improvement.

Now, what was the test?

Input Data:

public static final int[][] DATA = {
    {-1},
    {1},
    {-5, 1, -3, 7, -1, 2, 1, -4, 6},
    {-5, 1, -3, 7, -1, 2, 1, -6, 5},
    {-5, 6, -3, -2, 7, -5, 2, 1, -7, 6},
    {-5, -2, -1, -4, -7},
    {4, 1, 1, 4, -4, 10, -4, 10, 3, -3, -9, -8, 2, -6, -6, -5, -1, -7, 7, 8},
    {4, -5, -1, 0, -2, 20, -4, -3, -2, 8, -1, 10, -1, -1 },
    buildRandom(1000, -10, 100),
    buildRandom(10000, -10, 100),
    buildRandom(10000, -1, 10000)
};

the buildRandom method is defined as follows:

private static final int[] buildRandom(int size, int min, int max) {
    Random rand = new Random(size);
    int[] ret = new int[size];
    for (int i = 0; i < size; i++) {
        ret[i] = min + rand.nextInt(max - min + 1);
    }
    return ret;
}

For each input array, the system is warmed up, then run. The max-sum for the array is returned, and stored. Looking back to the performance output, we see all the tests had the result:

[-1, 1, 11, 9, 8, -1, 25, 28, 45769, 447857, 50645434]

They all got the maxsum for the input data as -1 for {-1}, 1 for {1}, 11 for {-5, 1, -3, 7, -1, 2, 1, -4, 6}, and so on.

The actual code to do these tests has been slightly modified from the CR Postings to return just the sum (not the array), and the code looks like:

Rolfl's:

    private static final int getMaxSum(int[] array) {
        int maxsum = Integer.MIN_VALUE;
//        int maxl = -1;
//        int maxr = -1;
        for (int left = 0; left < array.length; left++) {
            int sum = 0;
            for (int right = left; right < array.length; right++) {
                sum += array[right];
                if (sum > maxsum) {
                    maxsum = sum;
//                    maxl = left;
//                    maxr = right;
                }
            }
        }
    
        // if return just sum....
        return maxsum;
    
        // if return array:
        //return Arrays.copyOfRange(array, maxl, maxr + 1);
    }

Simon's

    private static int scanArray(int[] array) {
        if (array == null || array.length == 0)
            throw new IllegalArgumentException("Array cannot be null and must contain at least one element");
    
        //int maxStartingIndex = 0;
        //int maxEndingIndex = 0;
        int max = array[0];
    
        outer:
        for (int startLoop = 0; startLoop < array.length; startLoop++) {
            int value = array[startLoop];
            // To allow an array of all negatives, check if this value alone is more than the previous maximum.
            if (value > max) {
                max = value;
                //maxStartingIndex = startLoop;
                //maxEndingIndex = startLoop;
            }
    
            // If this value is below zero, there's no need in starting to loop here, it's better to start looping on a positive value.
            if (value < 0)
                continue;
            //System.out.println();
            //System.out.println(String.format("Starting looping on %d, max is %d for indexes %d -- %d", startLoop, max, maxStartingIndex, maxEndingIndex));
    
            int currentSum = value;
            for (int innerLoop = startLoop + 1; innerLoop < array.length; innerLoop++) {
                currentSum += array[innerLoop];
    
                // If we're below zero than there's no need to continue on this path.
                if (currentSum < 0) {
                    startLoop = innerLoop - 1;
                    break;
                }
    
                // Check for a new record
                if (currentSum > max) {
                    max = currentSum;
                    //maxStartingIndex = startLoop;
                    //maxEndingIndex = innerLoop;
                }
    
                //System.out.println(String.format("CurrentSum %d, i %d, j %d, max is %d for index %d -- %d", currentSum, startLoop, innerLoop, max, maxStartingIndex, maxEndingIndex));
    
                // Check if we have reached the end of the array. If we have, then there's no need in continuing the outer iterations. We know the max already
                if (innerLoop == array.length - 1) {
                    break outer;
                }
            }
        }
    
        return max; //Arrays.copyOfRange(array, maxStartingIndex, maxEndingIndex + 1);
    }

Simon & Rolfl

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

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

        int startLoop = 0;
        outer:
        while (startLoop < array.length) {
            int currentSum = 0;
            for (int innerLoop = startLoop; innerLoop < array.length; innerLoop++) {
                currentSum += array[innerLoop];

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

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

            }
            // we looped through to the end... there's no better solution.
            break outer;
        }

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

Simon Forsberg · Accepted Answer · 2015-10-01 12:26:30Z

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);
}

Should probably be posted for review. Just for example, given the rearrangement of the code, innerLoop is now a poor name since it's no longer an inner loop--or, arguably, it just shows that innerLoop never was a good name, reflecting the structure of the implementation instead of the intent. — Jerry Coffin, Jun 2, 2014 at 18:31
@JerryCoffin I didn't give much thought to the variable names, I edited and changed the variable name. Do you still think it should be posted for review? IMO this kinda feels as good as it can get. — Simon Forsberg, Jun 2, 2014 at 18:35
I do see one or two other (admittedly minor) issues, but it's up to you. — Jerry Coffin, Jun 2, 2014 at 18:45

Stack Exchange Network

Finding the sub-array with the maximum sum - my approach

My approach

4 Answers 4

Logic Duplication

Improvements

Performance

Performance Benchmarks

Your Answer

Not the answer you're looking for? Browse other questions tagged
java
performance
array
interview-questions
or ask your own question.

Linked

Hot Network Questions

Finding the sub-array with the maximum sum - my approach

My approach

4 Answers 4

Logic Duplication

Improvements

Performance

Performance Benchmarks

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
java
performance
array
interview-questions
or ask your own question.