max sum subarray

# maximum sum subarray
# Divide and Conquer from CLRS
# Idea is, after taking the midpoint maximum sub array
# is going to be in left subarray or right subarray or in a subarray spanning
# both left and right subarray crossing the midpoint.
# The above is well applicable for smaller instances of the
# original problem recursively leading to effective divide and conquer
# algorithm
def findMaxCrossingSubArray(A, low, high, mid):
    """
    Start from the midpoint, go towards left
    calculate the sum upto any index and return the maximum sum
    repeat the same for right side
    """
    leftsum = -9999999
    rightsum = -9999999
    l = 0
    h =0
    # left
    t=mid
    s = 0
    while t>=low:
        s=s+A[t]
        if s > leftsum:
           leftsum=s
            l = t
        t=t-1
        
    # right side
    t=mid+1
    s = 0
    whilet<=high:
        s=s+A[t]
        if s > rightsum:
            rightsum=s
            h=t
        t=t+1
   return (l, h, (leftsum+rightsum))
def findMaxSubArray(A, low, high):
    """
    Calculates the max subarray and returns the sum
   A - array
    low - left index to start with
    high - right index to start with
    """
    # base case occurs when low ==high
    # i.e. array has only one element
    if low == high:
        return (low, high, A[low])
    mid =(low+high)/2
    llow, lhigh, leftSum = findMaxSubArray(A, low, mid)
    rlow, rhigh, rightSum = findMaxSubArray(A, mid+1, high)
    clow,chigh, crossingSum = findMaxCrossingSubArray(A, low, high, mid)
    if leftSum > rightSum:
        if leftSum >crossingSum:
           return (llow, lhigh, leftSum)
        else:
            return (clow, chigh, crossingSum)
    else:
        if rightSum >crossingSum:
            return (rlow, rhigh, rightSum)
        else:
            return (clow, chigh, crossingSum)
A = [13, -3,-25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
print A
print findMaxSubArray(A, 0, len(A)-1)