Jim Driscoll's Blog

Notes on Technology and the Web

Using JDK 8 to get a sum of a list

with one comment

Another interview question, another chance to play with Java 8: “Given an array of integers (positive or negative) find the sub-array with the largest sum”.

Because arrays are a drag, let’s do this with a List. And note that the there’s no indication of whether the integers are bounded in size in any way. But again, because BigInteger is a bit a bit annoying to work with, I’m going to sidestep that as well (but JDK 8 provides a way to do that safely, as I’ll show in a second.)

First, we need to create that list of random numbers. In JDK 8 – it’s trivial:

List random
    = Collections.unmodifiableList(
        new Random()
        .ints(-100, 101)

This is so easy I hesitate to even go through it, but… Random has a new function, ints, which returns a Stream of random int values, between the given numbers (with end number exclusive). So, get a Stream of numbers from -100 to 100. limit stops the stream after it generates 2500 values. boxed changes the IntStream returned by ints into Stream. Lastly, convert it into a List, and make that list unmodifiable.

And as a reminder, if you want to dump out the values of this list to standard out, it’s as simple as:


We’ll also need a List summing function. The obvious way to do it is:

    public long sum(List<Integer> l) {
        long ret = 0;
        for (int i: l) {
            ret += i;
        return ret;

But Netbeans helpfully suggests that it can be converted into a functional method – which, after a bit of massaging, looks like this:

    public long sum(List<Integer> list) {
        return list.stream()
                .map((i) -> (long) i)
                .reduce(0L, (accumulator, _item)
                        -> accumulator + _item); 

Which is kinda neat – though it’s neither more readable (in my opinion) nor is it more performant (though it can be converted to parallel processing trivially, which is nice). Create a Stream, use a map method to cast each value to long, then reduce by adding all the values, returning that value.

But if the inputs are too large, it will return an incorrect value. In JDK 8, that’s easy to fix:

    public long sum(List<Integer> list) {
        return list.stream()
                .map((i) -> (long) i)
                .reduce(0L, (accumulator, _item)
                        -> Math.addExact(accumulator, _item)); 

The new Math.addExact method is a convenience method with a check for overflow – if the value overflows, an ArithmeticException is thrown (without a check, if the value overflows, you’ll get a freakish looking result, since 2’s complement is not how we’re used to thinking of numbers).

Our program will still fail if the numbers get too large (that’s the price of not using BigInteger), but at least now, it’ll tell us, instead of silently spitting out bad data.

On to solving the problem. Remember: “First, make it work. Then, make it work fast.” The naive solution is pretty simple, just a couple loops:

long resultValue = list.get(0); // seed value
long numTries = 0;

for (int start = 0; start < list.size(); start++) {
    for (int end = start; end < list.size(); end++) {
        List<Integer> tester = list.subList(start, end + 1);
        long testresult = sum(tester);
        if (testresult > resultValue) {
            resultValue = testresult;

But this solution is pretty slow. The numTries variable increases at a frightening pace as the size of the dataset examined goes up. If you remember back to your CompSci homework assignments, it’s Triangular Number (which is essentially like a factorial, except using the sum instead of the product). That’s still O(n2) in Big O. We’re certainly going to want to make it faster. (On my machine, a list of 2500 random numbers takes a glacial 25 seconds to complete.)

Well, I’ve got 8 cores and I’m not afraid to use them. Let’s do parallel processing. At first, I looked into doing something with Streams. While I think it’d be possible to do this, I don’t think it’s advised – that doesn’t look like what Streams were meant to do. If I was writing some sort of framework code, it might be something to look into, but for now, just using Futures will probably do:

ForkJoinPool pool = ForkJoinPool.commonPool();
List<Future> futures = new ArrayList<>();
AtomicLong resultValue = new AtomicLong(list.get(0));  // seed value
LongAdder numTries = new LongAdder();

for (int start = 0; start  {
        for (int end = s; end < list.size(); end++) {
            List<Integer> tester = list.subList(s, end + 1);
            long testresult = sum(tester);
            resultValue.accumulateAndGet(testresult, (x, y) -> {
                return (x > y) ? x : y;
for (Future f : futures) {

All right, there’s a few late-model JDK things going on in there, so let’s unpack them. The ArrayList declaration uses the diamond operator from JDK 7. The LongAdder class is new in JDK 8, and it’s pretty easy to understand what it does. It’s a faster alternative for accumulators (counters) in multithreaded environments, since under the hood it might even be several different variables that only collapse into one when you want to see the total value.

ForkJoinPool is a threading pool class from JDK 7 (it implements ExecutorService), and the commonPool method is new in JDK 8: it returns a pre-fab pool of threads for easy use. Just the thing for example programs, or anywhere else where you know your code is the only thing running in the VM. The submit method is the same venerable one from ExecutorService, but as you can see, you can feed it a lambda expression, with is way more convenient than an anonymous inner class (once you get used to them, and they’re starting to grow on me).

Because we’re feeding it a lambda that’s going to reference the start value, we need to fix that value, to promise it won’t change. We could write some extra code to get the lambda to take a parameter, but that’s work, and will decrease readability besides. So we can just fix the value into a new final variable, and access it without issue.

Actually dealing with the futures we’re creating is easy enough – just cycle through them in turn, waiting for them to complete (which is all that the get method is doing). We could return the value found, and get the max after they’re all complete, but I thought it might be more fun to examine another way, with AtomicLong. (Obviously, I’ve got some odd ideas of fun, but I’m an engineer, so that goes without saying.)

AtomicLong has a handful of new, lambda loving functions in JDK 8: I’m using accumulateAndGet, which I use to update the value of the long if the new value is greater than the current value. This will also return the new, updated value, but that’s safely ignored until the end of the process.

When all this is done, I’ve got a considerably faster program (about 7 seconds on my machine), and it’s not much more complicated… I’m loving what they’ve done here with threading.

But 7 seconds is still a pretty long time to search 2500 values. There’s got to be a better way – and of course, there is: interview questions are puzzles, and it’s rare that a detail of a puzzle is just there to mislead you. In this case, the question included that there are negative and positive numbers in the list.

Well, adding a negative number to a sum is never going to help matters, so if we just leave that operation out, we should be able to reduce the total number of searches considerably down from the 3 million or so that you get with 2500 values.

long resultValue = list.stream().max(Integer::compare).get(); // seed value
long numTries = 0;

for (int start = 0; start  0) {
        for (int end = start; end  0) {
                List tester = list.subList(start, end + 1); // sublist uses exclusive end
                long testresult = sum(tester);
                if (testresult > resultValue) {
                    resultValue = testresult;

This is essentially the same program as the first, with a few small changes: We’re changing the seed value to calculate the maximum value (which we need to do to in case all the numbers are negative), and the there are a couple of added checks – if a value is negative or zero, it’s not going to increase the sum, so we can safely skip those computations. Calculating the max first is more inefficient than doing it at the end, but in a O(n2) function (which this still is), that’s more or less noise, and this way increases readability.

That last .get(), by the way, is because the value returned is an Optional (also new in JDK 8) – if the List is empty, there might be nothing to return. This is essentially a way around the “sideband return value” problem – API designers are always needing to come up with a way to indicate “nothing found”. JDK 8 finally offers a standard way to do that. Since we’re in control of inputs, we’re confident that something will be there, so we’re just going to sidestep that for now. (But read on.)

On my machine, that drops the execution time to about 6 seconds. With futures, we can do it even faster. While we’re at it, we’ll use another new JDK 8 feature, CompletableFutures.

List<Future<Long>> futures = new ArrayList<>();
LongAdder numTries = new LongAdder();

for (int start = 0; start  0) {
        futures.add(CompletableFuture.supplyAsync(() -> {
            long maxresult = list.get(s); //seed
            for (int end = s; end  0) {
                    List tester = list.subList(s, end + 1);
                    long testresult = sum(tester);
                    if (maxresult  maxresult) {
                    maxresult = testvalue;
            return maxresult;
        }).exceptionally(ex -> {
            if (ex.getCause() instanceof ArithmeticException) {
                return Long.MAX_VALUE;
            } else {
                throw (RuntimeException) ex;
long result = futures.stream()
        .map(f -> {
            try {
                return f.get();
            } catch (InterruptedException | ExecutionException e) {
                throw new RuntimeException(e);
        // if all values are negative, get the biggest one
        .orElseGet(() ->(long)list.stream().max(Integer::compare).get());

OK, that's a big lump of code. Let's break it down:

We're creating a List of Futures which return Long – that means that instead of just having the futures update a shared variable, they'll produce individual results. We'll instead process the values at the end.

You'll note that the explicit reference to ForkJoinPool is gone, but it's still in use – it's implicit in the call to CompletableFuture.supplyAsync (and you can instead specify a different ExecutorService, if you need one). supplyAsync takes a Supplier lambda, which is just a fancy way of saying "give it a no-args function that returns a value". In this case, we're returning a long, which fits our declaration that it's a Future, and the compiler will helpfully kvetch at us if it isn't.

The CompletableFuture has lots of methods for chaining, which is where it really shines. In our case, we want to intercept things if there's an exception, and override the result if it's an overflow. Here, we use the handle method do that. For our contrived example, if there's an overflow, we'll just stub in the maximum Long value – in a "real" program, maybe you'd even do the work to drop back to using BigInteger, or you could update a shared error value. Completable futures also let you chain things with methods like andThen, which executes a further task on the returned result, or andThenAsync, which lets you do the same thing, except by spawning yet another threaded task. It's a pretty nifty little class, and it's not hard to see it making parallel programming much, much easier.

I found a particularly excellent writeup on Completable Futures by Tomasz Nurkiewicz, or you could just go ahead and get Cay’s book, Java 8 For the Really Impatient, which as I’ve mentioned before is really awesome.

Other changes in the body of the program are primarily around restricting calls away from non-positive integers, and computing seed values.

The last part of the program is just another Stream reader to compute the maximum value – with a twist at the end. As the interim step, we read all the futures via Future.get(), and we need to check for the checked exceptions that throws – note the JDK 7 multi-catch. Then we compute the maximum value returned, and we’re done – almost.

If all the values are negative, there won’t be anything returned in the Stream, since our incredibly efficient program will ignore all of those values. What do do? Since the returned value from the stream is an Optional, we can write a small function (as a lambda) that will compute the maximum value of all those negative numbers, and that becomes our answer.

And what does all this get us? A much faster program: about 2 seconds on my (admittedly butch) machine, though I also get an additional 300 millseconds or so in savings if the thread pool is already warmed up.

All this code is up on a gist, if you want to read it in it’s entirety and try it out for yourself.

Written by jamesgdriscoll

January 4, 2014 at 11:46 AM

One Response

Subscribe to comments with RSS.

  1. In order to sum integer/long values of a list a simpler approach would be:
    longList.stream().mapToLong(aLong -> aLong).sum()


    June 15, 2015 at 3:07 AM

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 413 other followers

%d bloggers like this: