In [20]:

    

def findMaxCrossingSubArray(A, lo, mid, hi):    
    maxLeft, maxRight = mid, mid + 1
    maxSumLeft, maxSumRight, sumLeft, sumRight = 0, 0, 0, 0
    for i in range(mid, lo, -1):
        sumLeft = sumLeft + A[i]
        if maxSumLeft < sumLeft:
            maxSumLeft = sumLeft
            maxLeft = i
    for i in range(mid + 1, hi):
        sumRight = sumRight + A[i]
        if maxSumRight < sumRight:
            maxSumRight = sumRight
            maxRight = i
    return (maxLeft, maxRight, maxSumLeft + maxSumRight)


    

In [41]:

    

from math import floor

def findMaxSubarray(A, lo, hi):
    if lo == hi:
        return (lo, hi, 0)
    else:
        mid = int(floor((lo + hi)/2))
        leftLo, leftHi, leftSum = findMaxSubarray(A, lo, mid)
        rightLo, rightHi, rightSum = findMaxSubarray(A, mid + 1, hi)
        crossLo, crossHi, crossSum = findMaxCrossingSubArray(A, lo, mid, hi)
        if leftSum >= rightSum and leftSum >= crossSum:
            return (leftLo, leftHi, leftSum)
        elif rightSum >= crossSum and rightSum >= leftSum:
            return (rightLo, rightHi, rightSum)
        else:
            return (crossLo, crossHi, crossSum)


    

In [42]:

    

A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
print(findMaxCrossingSubArray(A, 0, (int)((0 + len(A))/2), len(A)))
print(findMaxSubarray(A, 0, len(A)))


    

    




(7, 10, 43)
(7, 10, 43)

In [ ]: