Programming Challenge SolutionThis 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. |