import math

def FIND_MAX_CROSS_SUBARRAY(A,low,mid,high):
    left_sum = math.inf*-1
    tsum = 0
    for i in range(mid,low-1,-1):
        tsum = tsum + A[i]
        if (tsum > left_sum):
            left_sum = tsum
            max_left = i
    right_sum = math.inf*-1
    tsum = 0
    for j in range(mid+1,high+1):
        tsum = tsum + A[j]
        if (tsum > right_sum):
            right_sum = tsum
            max_right = j
    return(max_left,max_right,left_sum+right_sum)


def FIND_MAX_SUBARRAY(A,low,high):
    if (high == low):
        return (low,high,A[low])
    else:
        mid = math.floor((low+high)/2)
        (left_low,left_high,left_sum) = FIND_MAX_SUBARRAY(A,low,mid)
        (right_low,right_high,right_sum) = FIND_MAX_SUBARRAY(A,mid+1,high)
        (cross_low,cross_high,cross_sum) = FIND_MAX_CROSS_SUBARRAY(A,low,mid,high)
        if (left_sum >= right_sum) and (left_sum >= cross_sum):
            return (left_low,left_high,left_sum)
        elif (right_sum >= left_sum) and (right_sum >= cross_sum):
            return (right_low,right_high,right_sum)
        else: return (cross_low,cross_high,cross_sum)

def main():
    print("Find Maximum Subarray")
    A = eval(input('Enter array:'))
    (i, j, max_sum) = FIND_MAX_SUBARRAY(A,0,len(A)-1)
    print("Output(i,j,max_sum,A[i:j]): ",i,j,max_sum,A[i:j+1])

main()