maxSubArray.py

def maxSubArray(A):
    T = A[0]
    S = T
    for i in range(1, len(A)):
        T = A[i] + max(T, 0)
        S = max(S, T)

    return S

if __name__ == '__main__':
    A = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print(maxSubArray(A))

notes.txt

Let A the the array.
Let T(i) be the sum of the maximum subarray with A[i] as the final element.
Let S(i) be the sum of the maximum subarray in the subarray zero through i.

Then T(i) = {
	A[0]                  if i == 0
	A[i] + max(T(i-1), 0) if i > 0
}

The intution here is that we can extend the subarray ending at i-1 to i by
adding the element A[i]. However, it may be the case that the sum at T(i-1) is
so low that we may choose to drop it entirely, meaning the subarray with largest
sum that ends at i is simply A[i] alone.

And S(i) = max(T(j)) for all j <= i.

Using the definition of max to our advantage, we can re-express S(i) as a
piecewise recurrence.

We have S(i) = {
	T(i)              if i == 0
	max(S(i-1), T(i)) if i > 0
}

The intuition here is that we already know the subarrays with maximum sum that
end at each index of the array. Becuase the final answer necessarily ends at one
of those indices, we can simply choose the best one.

Then S(n-1) will be the final result we want.

Finally, observe that none of these recurrences look behind further than one
index at a time. This means we don't even have to store the full table --
instead we can have scalars for S and T that represent their most recent value.