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

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 parameters() {
List 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);

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

StackExchange Code Review Q#52270, answer score: 13