def _max_profit_crossing(lst: list[int], left: int, right: int, mid: int): # O(n)
    """
    Our helper function to max_profit().
    Requires O(n) time and space as it iterates through our left and right sublists to find the best price.
    """
    left_sum = 0
    total = 0
    # Starting from the middle, find the best price moving left.
    for i in range(mid, left - 1, -1):
        total += lst[i]
        if total > left_sum:
            left_sum = total

    right_sum = 0
    total = 0
    # Starting from just after the middle, find the best price as we iterate to the right.
    for j in range(mid+1, right+1):
        total += lst[j]
        if total > right_sum:
            right_sum = total
    
    # Return the sum of our best prices in either sublist:
    return left_sum + right_sum