import math


def maxsubarrayMid(list, start, mid, end):
    """
    Find the max subarray that crosses the mid point given
    Do this by naively finding the max subarray on the left side
    ending at position mid, and finding the max subarray on the 
    right side starting at position mid

    Time complexity: O(length if input)
    """
    leftMaxSum = -math.inf
    leftSum = 0
    leftIndex = mid
    # Find the left max subarray ending at mid
    for i in range(mid, start - 1, -1):
        leftSum += list[i]
        if leftSum > leftMaxSum:
            leftMaxSum = leftSum
            leftIndex = i

    rightMaxSum = -math.inf
    rightSum = 0
    rightIndex = mid
    # Find the right max subarray starting at mid
    for i in range(mid + 1, end + 1):
        rightSum += list[i]
        if rightSum > rightMaxSum:
            rightMaxSum = rightSum
            rightIndex = i
    
    # Security checks in case there was no left/right subarray
    # This is for the edge cases when we have odd number of elements
    maxSum = 0
    if leftMaxSum != -math.inf:
        maxSum += leftMaxSum
    if rightMaxSum != -math.inf:
        maxSum += rightMaxSum
    return (maxSum, leftIndex, rightIndex)