In [30]:

    

import sys

def find_maximum_subarray(arr):
    max_sum = -sys.maxsize
    max_left, max_right = -1, -1
    sum = 0
    last_left = 0
    for i in range(len(arr)):
        sum += arr[i]
        if sum > max_sum:
            max_sum = sum
            max_left = last_left
            max_right = i
        if sum < 0:
            sum = 0
            last_left = i + 1
    return max_left, max_right, max_sum


    

In [31]:

    

print(solve([1, 2, -4, 2, 2]))


    

    




maxFromLeft 1 indexOfMaxFromLeft 0 maxFromRight 1 indexOfMaxFromRight 0
maxFromLeft 3 indexOfMaxFromLeft 1 maxFromRight 2 indexOfMaxFromRight 1
maxFromLeft 3 indexOfMaxFromLeft 1 maxFromRight 0 indexOfMaxFromRight 2
maxFromLeft 3 indexOfMaxFromLeft 1 maxFromRight 2 indexOfMaxFromRight 3
maxFromLeft 3 indexOfMaxFromLeft 1 maxFromRight 4 indexOfMaxFromRight 3
(4, 3, 5)

In [ ]: