• 1

• 75.5k
• 18
• 194
• 467

• 98.1k
• 17
• 219
• 419

#Performance Benchmarks

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

1. My answer to the original quesiton
2. Simon's answer with the code in this question.
3. 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);
 }