Subarray de soma máxima

Dado um array de n inteiros, encontre um subarray contíguo que apresente a maior soma de valores.

Entrada

A primeira linha da entrada contém um inteiro n – o número de elementos no array (1 ≤ n ≤ ).

A linha seguinte contém n inteiros separados por espaço, que representam os elementos do array .

Saída

O programa deve imprimir apenas um inteiro – a maior soma possível entre todos os subarrays do array fornecido.

Exemplos

Explicação

1. -2 1 -3 4 -1 3 1 -4 -2 → A soma do subarray em destaque é (4 - 1 + 3 + 1) = 7

2. 1 -2 3 4 -3 1 7 -10 -20 4 → 3 + 4 -3 + 1 + 7 = 12