Computer Science Puzzle: Finding the Maximal Sum of a Vector

Posted on April 4, 2008
Filed Under Computer Puzzles, Computer Science |

While this is a physics-oriented blog, computer science has some great puzzles, too! If you’re a professional computer scientist they’ll probably be easy for you, or you’ll already know the answer, but for anyone who isn’t familiar with the ropes, they can be very challenging. It’s always good to learn something new, too.

This week’s puzzle is about finding the maximal sum of a vector. Suppose you are given a vector (x(1),x(2),x(3),….,x(N)) of numbers, which can be positive or negative (or zero). You’re interesting in finding the vector’s maximal sum, meaning: starting out from an index i and ending at an index j, you want the sum of x(i)+x(i+1)+….+x(j) to be maximal.

 What is the fastest algorithm you can devise for this? Can you find an algorithm log-linear in N? Can you find anything faster?

This would be an easy puzzle if the x(i)s were all positive numbers: then you’d just sum all of them!

X = (5,9,1,20,4)  –>  maximal sum = 5+9+1+20+4.

However, when you introduce negative numbers into the game, it complicates things significantly:

X = (5,9,1,-20,4)  –> 5+ 9 + 1 + (-20) + 4 is obviously not maximal. 5+9+1 IS.

Good luck & enjoy! :)

Comments

One Response to “Computer Science Puzzle: Finding the Maximal Sum of a Vector”

  1. admin on April 11th, 2008 5:01 am

    Solution (ADDED 11/4/2008)
    ————————–

    The naive approach would be to examine all possible subvectors of the given vector. There are (2 choose N)=N!/(2!*(N-2)!) ~ N^2 ways of doing that. Then you have to sum each vector, which costs ~ N/2 on the average, and keep track of the maximum, so the overall performance of the algorithm is O(N^3). Not very good.

    There are many ways of improving the algorithm. The best solution is O(N), going inductively through the vetor step by step:

    “Given that you’ve solved the problem for j, solve the problem for j+1.”

    We’re going to do that by keeping tabs on TWO quantities:
    1. The maximal sum so far, maxsofar.
    2. The maximal sum that ends at j, maxending.

    For example, for the vector (2 3 6 -17 8 2 -2) for which N=7, for the step j=6, maxsofar would the the sum of the first three numbers, 2+3+6=11. maxending would be the maximal subvector that ends at j=6, that is, at the value +2. That is obviously 2+8, since going back further would just diminish this sum.

    For the j-th step, these two variables are updated as follows:

    maxending = max(maxending + x[j+1], 0)
    maxsofar = max(maxsofar, maxending)

    The insight here is that, whenever we step forward from j to j+1, there are only two possibilities: either our maximal sum is what we’ve computed so far, or it must come from the new term added, which affects maxending.

    (Obviously, for j=0, initially both maxending = 0 and maxsofar=0.)

Leave a Reply