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

}