In [4]:

    

import sys

def findMaxCrossingSubArray(A, lo, mid, hi):    
    maxSumLeft, maxSumRight, sumLeft, sumRight = -sys.maxsize, -sys.maxsize, 0, 0
    for i in range(mid, lo - 1, -1):
        sumLeft = sumLeft + A[i]
        if maxSumLeft < sumLeft:
            maxSumLeft = sumLeft
    for i in range(mid + 1, hi):
        sumRight = sumRight + A[i]
        if maxSumRight < sumRight:
            maxSumRight = sumRight
    totalSum = maxSumLeft + maxSumRight
    if totalSum >= maxSumLeft and totalSum >= maxSumRight:
        return totalSum
    elif maxSumLeft >= totalSum and maxSumLeft >= maxSumRight:
        return maxSumLeft
    else:
        return maxSumRight


    

In [2]:

    

from math import floor
import sys

def findMaxSubarray(A, lo, hi):
    if lo == hi:
        return -sys.maxsize
    else:
        mid = int(floor((lo + hi)/2))
        leftSum = findMaxSubarray(A, lo, mid)
        rightSum = findMaxSubarray(A, mid + 1, hi)
        crossSum = findMaxCrossingSubArray(A, lo, mid, hi)
        if leftSum >= rightSum and leftSum >= crossSum:
            return leftSum
        elif rightSum >= crossSum and rightSum >= leftSum:
            return rightSum
        else:
            return crossSum


    

In [8]:

    

A = [1, 2, 3, 4]
B = [2, -1, 2, 3, 4, -5]
C = [-5, -4, -3, -2, -1]
print(findMaxSubarray(C, 0, len(C)))


    

    




-1

In [ ]: