Envío 2235

Código

def find_best(a):
  n = len(a)
  # Caso base
  if n == 1:
    return a[0]

  half = n // 2

  left = a[0:half]
  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_right = a[half]
  for i in range(half+1, n):
    sum_right += a[i]
    best_sum_right = max(best_sum_right, sum_right)

  # 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)


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