In [45]:

    

import sys

def findMaxCrossingSubarray(A, low, mid, high):
    leftSum, sum, maxLeft = -sys.maxsize, 0, mid
    for i in range(mid, low - 1, -1):
        sum = sum + A[i]
        if sum > leftSum:
            leftSum = sum
            maxLeft = i
    rightSum, sum, maxRight = -sys.maxsize, 0, mid + 1
    for j in range(mid + 1, high + 1):
        sum = sum + A[j]
        if sum > rightSum:
            rightSum = sum
            maxRight = j
    return maxLeft, maxRight, leftSum + rightSum


    

In [42]:

    

def findMaximumSubarray(A, low, high):
    if high == low:
        return low, high, A[low]
    else:
        mid = math.floor((low + high)/2)
        leftLow, leftHigh, leftSum = findMaximumSubarray(A, low, mid)
        rightLow, rightHigh, rightSum = findMaximumSubarray(A, mid + 1, high)
        crossLow, crossHigh, crossSum = findMaxCrossingSubarray(A, low, mid, high)
        if leftSum >= rightSum and leftSum >= crossSum:
            return leftLow, leftHigh, leftSum
        elif rightSum >= leftSum and rightSum >= crossSum:
            return rightLow, rightHigh, rightSum
        return crossLow, crossHigh, crossSum


    

In [49]:

    

import math

#A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
A = [1, -4, 3, -4]
#print(findMaxCrossingSubarray(A, 0, math.floor(len(A)/2), len(A)-1))
print(findMaximumSubarray(A, 0, len(A) - 1))


    

    




(2, 2, 3)

In [ ]: