Maximum subarray problem demonstration

maxsubarr.py

def max_of_array_ending_at(array, p):
    if p == 0:
        return array[0] if array[0] > 0 else 0

    subproblem = max_of_array_ending_at(array, p-1)

    if subproblem + array[p] > 0:
        return subproblem + array[p]
    else:
        return 0

def maximum_subarray_problem(array):
    return max(max_of_array_ending_at(array, p) for p in range(len(array)))

def iterative_version(array):
    max_ending_here = 0
    max_total = 0

    for n in array:
        if max_ending_here + n > 0:
            max_ending_here += n
        else:
            max_ending_here = 0

        max_total = max(max_total, max_ending_here)

    return max_total

if __name__ == "__main__":
    array = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

    print maximum_subarray_problem(array)
    print iterative_version(array)