Maximum Subarray Problem

Maximum Subarray Problem.py

let A be the given array of integers
let maxSum = -infinity, maxLeft = 0, maxRight = 0, currentMax = 0, left = 0, right = 0
for i = 0 to A.length - 1
  currentMax += A[i]
  if currentMax > maxSum
    maxSum = currentMax
    right = i;
    maxLeft = left
    maxRight = right
  if currentMax < 0
    currentMax = 0
    left = i + 1
    right = i + 1
A[maxLeft...maxRight] is the maximum sum contiguous subarray.
return maxSum