Submission for the 2013-05-03 UpFront Code Challenge

max_subarray.py

def max_subarray(A):
    max_ending_here = max_so_far = 0
    neg_high = A[0]
    all_neg = True
    for x in A:
        if x > 0: 
            all_neg = False
            break
        else:
            if x > neg_high:
                neg_high = x
    if all_neg:
        return neg_high
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

print max_subarray([-4, 5, 5, -7, 4, -1, 8, -6])
print max_subarray([2, -3, 6, 5, -1, 2, -4, 3])
print max_subarray([2, 5, -8, -3, 8, -2, -9, 7])
print max_subarray([-4, -3, 6, 6, -9, 4, -9, 8])
print max_subarray([-4, -3, -2, -1, -7, -4, -9, -3])