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