Subarray 3

Límite de tiempo: 1000 ms

Límite de memoria: 128 MiB

Se te dará un array con enteros positivos y negativos, halla la mayor suma de elementos en un subarray no vacío.

Recuerda que un subarray es un rango continuo de elementos dentro del array.

Entrada

La primera línea contiene un entero $n$ ( $1 \leq n \leq 10^{5}$ ), el número de elementos del array.

La segunda línea contiene $n$ enteros $a_{1}, a_{2}, \dots, a_{n}$ ( $- 10^{9} \leq a_{i} \leq 10^{9}$ ), los elementos del array.

Un solo entero, la mayor suma de elementos en un subarray no vacío.

Entrada

5
-1 2 -1 4 -7

Salida