Encuentra la mayor suma posible de un subarreglo (un tramo contiguo y no vacío) del arreglo dado.

Entrada

La primera línea tiene \(n\) \((1 \le n \le 10^5)\) y la segunda los \(n\) enteros \((|a_i| \le 10^4)\).

Salida

La suma máxima.

Ejemplo 1

Entrada

9
-2 1 -3 4 -1 2 1 -5 4

Salida

6

Ejemplo 2

Entrada

1
1

Salida

1

Ejemplo 3

Entrada

5
5 4 -1 7 8

Salida

23

Basado en el problema 53 de LeetCode, Maximum Subarray, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.