Find Largest Sum of Contiguous Numbers in an Array

This is one popular interview question. The problem: given an array which could contain zero, negative, and positive numbers, find the largest sum of contiguous sub-array. For example, if the array contains:

    31, -41, 59, 26, -53, 58, 97, -93, -23, 84
		

then the largest sum is 187 taken from the [59 .. 97] block

My research points to Jon Bentley’s solution as the most efficient solution (see his book, “Programming Pearls”). In fact, Bentley was probably the person who started this thread. His solution has a complexity of O(n) which is very good, considering the brute force solution is of O(n³). Here is a Python implementation of Bentley’s solution:

def largest(array):
    maxSoFar = maxUpToHere = 0

    for element in array:
        maxUpToHere= max(maxUpToHere + element, 0)
        maxSoFar = max(maxSoFar, maxUpToHere)

    return maxSoFar

This solution is very efficient, short, and easy to remember. To understand it, I recommend reading his book, “Programming Pearls.”

After implementing this solution, I wrote some test cases to verify its correctness. Overall, the code works well, but it does not return the correct value for cases when the whole array contains only negative numbers. For example, consider this array:

    -3, -1, -2

I expect to see -1 as the largest sum, but instead, I got 0. After studying the algorithm, I noticed that the problem comes from the line:

    maxUpToHere= max(maxUpToHere + element, 0)

For negatives-only cases, maxUpToHere will be zero because it is the larger of the two. Instead of zero, the correct output in these cases should be the largest number in the array. I also noticed that negatives-only are the only cases which cause trouble, so we can add detection to the code and return the largest element instead of maxSoFar. Here is the patched code:

# This is based on Bentley’s Programming Pearls
# My (Hai Vu’s) modification: if the array is all negatives
# then max is the largest element
def largest(array):
    maxSoFar = maxUpToHere = 0
    largestElement = array[0]
    allNegatives = True
    for element in array:
        maxUpToHere= max(maxUpToHere + element, 0)
        maxSoFar = max(maxSoFar, maxUpToHere)
        largestElement = max(largestElement, element)
        if element >= 0:
            allNegatives = False
    if allNegatives:
        return largestElement
    return maxSoFar

The patched code works well for all cases. However, if you have a better solution, I would like to learn about it. My python program is available for download: largestsumpy.pdf