import sys

def solve(a, l, r):
    if l == r:
        return a[l]

    mid = l + (r - l) // 2

    left = solve(a, l, mid)
    right = solve(a, mid + 1, r)

    sum_val = 0
    lmax = -sys.maxsize - 1
    for i in range(mid, l - 1, -1):
        sum_val += a[i]
        lmax = max(lmax, sum_val)

    sum_val = 0
    rmax = -sys.maxsize - 1
    for i in range(mid + 1, r + 1):
        sum_val += a[i]
        rmax = max(rmax, sum_val)

    return max(left, right, lmax + rmax)

if __name__ == "__main__":
    a1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    print(solve(a1, 0, len(a1)-1))

    a2 = [-5, -3, -1, -4]
    print(solve(a2, 0, len(a2)-1))

    a3 = [10]
    print(solve(a3, 0, 0))