Maximum Contiguous Sum in Python

README.md

Maximum Contiguous Sum

The problem was to find the maximum contiguous sum of series of numbers.

$ pip install pytest
$ py.test --doctest-modules

max_contiguous_sum.py

def max_sum(numbers):
    """
    Compute the max contiguous sum of the given numbers.

    >>> max_sum([-1, 5, 6, -2, 20, -50, 4])
    29
    >>> max_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4])
    6
    """
    if not numbers:
        return 0

    max_found = current = numbers[0]

    for n in numbers[1:]:
        current = max(0, current) + n
        max_found = max(max_found, current)

    return max_found

max_contiguous_sum_test.py

from max_contiguous_sum import max_sum


def test_given_numbers_should_return_the_max_contiguous_sum():
    assert max_sum([]) == 0
    assert max_sum([1]) == 1
    assert max_sum([-1]) == -1
    assert max_sum([1, 2]) == 3
    assert max_sum([1, 2]) == 3
    assert max_sum([1, 2, -1]) == 3
    assert max_sum([1, 2, -1, -1, 4]) == 5
    assert max_sum([-1, 2]) == 2
    assert max_sum([1, 2, -1, -1, 4, -20, 10]) == 10
    # Test cases found elsewhere to battle test the algorithm
    assert max_sum([1, 100, -50, -50, 100, 1]) == 102
    assert max_sum([0, 0, 0]) == 0
    assert max_sum([-3, -5, -10, -2, -7]) == -2
    assert max_sum([-50, -50, 100, 2]) == 102
    assert max_sum([-1, -1, -1, 0, -1, -1]) == 0