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

Question

I decided to give the maximum sub-array sum problem an interesting go, however I will assure you that it doesn't perform well, and that I would never put this in production.

I'd like a review on this, if possible, it would be cool to see the running time, I'm sure it's upper bounded by at most \$O(n^3)\,ドル but it may actually be less:

public class FindMaximumSubArraySumProblem extends Problem<int[]> {
 private 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)
 };
 private static int[] buildRandom(int size, int min, int max) {
 return new Random().ints(size, min, max).toArray();
 }
 public FindMaximumSubArraySumProblem() {
 super("Find Maximum Sub-array Problem", 1000, 10000);
 }
 @Override
 public String getResult() {
 return Arrays.toString(execute());
 }
 @Override
 public int[] execute() {
 return Arrays.stream(DATA).mapToInt(this::computeMaxSum).toArray();
 }
 private int computeMaxSum(final int[] array) {
 return IntStream.range(0, array.length)
 .map(i -> IntStream.range(i, array.length)
 .map(j -> Arrays.stream(array)
 .skip(i)
 .limit(j - i + 1)
 .sum()
 )
 .max()
 .orElse(0)
 )
 .max()
 .orElse(0);
 }
}

The method to look at is computeMaxSum:

private int computeMaxSum(final int[] array) {
 return IntStream.range(0, array.length)
 .map(i -> IntStream.range(i, array.length)
 .map(j -> Arrays.stream(array)
 .skip(i)
 .limit(j - i + 1)
 .sum()
 )
 .max()
 .orElse(0)
 )
 .max()
 .orElse(0);
}

Results are:

Find Maximum Sub-array Problem => [-1, 1, 11, 9, 8, -1, 25, 28] (hot 0,09256ms - cold 0,132ms (total 1028,825ms))

Answer 1

You code :

private static int[] buildRandom(int size, int min, int max) {
 return new Random().ints(size, min, max).toArray();
}

I think that doing new Random several times, will reduce the "randomness" of the output. You can read that Stack Overflow question for more information. The idea is to remove the new Random() and use the same instance to produce several output. I would suggest to have an instance of Random in your class FindMaximumSubArraySumProblem but then does it make sense to have it ? Not really. So this method look kind of odd in your class. You could move it in his own helper class where it would make more sense, and then extract an instance of Random to increase randomness.

• skiwi: Just a heads up: I do know about the dead code, I left it in on purpose as it can actually be used. The only issue is that the computation time then gets a bit long.