max_subarray.py

"""Maximum Subarray Problem

The maximum subarray problem is the task of finding the largest
possible sum of a contiguous subarray, within a given one-dimensional
array A[1…n] of numbers.

https://link.medium.com/MPXDJMtDMU
"""

def maxsubarray(array):
    max_global = float('-inf')
    max_local = 0

    if not array:
        return None

    for n in array:
        max_local = max(n, n + max_local)
        if max_global < max_local:
            max_global = max_local
    return max_global


def maxsubarray_2(array):
    max_global = float('-inf')
    max_local = 0

    if not array:
        return None

    j, k = 0, 0
    for i in range(len(array)):
        n = array[i]
        max_new = n + max_local
        if max_new > n:
            max_local = max_new
        else:
            max_local = n
            j = i

        if max_global < max_local:
            max_global = max_local
            k = i

    return array[j:k + 1]


def test_maxsubarray():
    test_array = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    assert maxsubarray(test_array) == 6


def test_maxsubarray_2():
    test_array = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    assert maxsubarray_2(test_array) == [4, -1, 2, 1]


if __name__ == '__main__':
    test_array = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print(maxsubarray(test_array))
    print(maxsubarray_2(test_array))
    print()

Output:

$ python3 max_subarray.py 
6
[4, -1, 2, 1]

$ pytest -v max_subarray.py 
======================================================== test session starts =========================================================
platform linux -- Python 3.7.2, pytest-4.3.0, py-1.8.0, pluggy-0.9.0 -- /home/gordonchiam/.linuxbrew/opt/python/bin/python3.7
cachedir: .pytest_cache
rootdir: /home/gordonchiam/Projects/max-subarray, inifile:
collected 2 items                                                                                                                    

max_subarray.py::test_maxsubarray PASSED                                                                                       [ 50%]
max_subarray.py::test_maxsubarray_2 PASSED                                                                                     [100%]

====================================================== 2 passed in 0.02 seconds ======================================================