Envío 2329

Código

"""Divide and conquer"""

def find_best(a):
    n = len(a)
    # Caso base
    if n == 1:
        return a[0]
    half = n // 2
    left = a[0:half] # cuando n es impar tiene un elemento menos que right
    right = a[half:]

    # Caso Recursivo ("Divide")
    best = max(find_best(left), find_best(right))

    # "Conquer"
    best_sum_left = a[half - 1]
    sum_left = a[half - 1]
    for i in range(half - 2, -1, -1):
        sum_left += a[i]
        best_sum_left = max(best_sum_left, sum_left)

    best_sum_right = a[half]
    sum_rigth = a[half]

    for i in range(half + 1, n):
        sum_rigth += a[i]
        best_sum_right = max(best_sum_right, sum_rigth)
    
    # La suma del mejor subarreglo que cruza la linea roja es best_sum_left + best_sum_right
    return max(best, best_sum_left + best_sum_right)
    
    return 0


n = int(input())
a = [int(x) for x in input().split()]

print(find_best(a))