Programming Challenge Solution

This can be solved in O(n) time using the following code that makes only a single pass over the array:

int max_sum(int *vector, int len)
{
    int best = 0, current = 0;
    int i = 0;
    for(i = 0; i < len; ++i)
    {
        current += *(vector + i);
        if(current < 0)
        {
            current = 0;
        }
        best = best > current ? best : current;
    }
    return best;
}

Download source

If you like this problem, I would highly recommend you take a look at the book from which I originally learned of the problem, Programming Pearls by Jon Bentley.