Le mucche hanno aperto una nuova attività e Farmer John vuole vedere come sta andando. L’attività è in funzione da $N$ ($1 \leq N \leq 100{,}000$) giorni e ogni giorno $i$ le mucche hanno registrato il loro profitto netto $P_i$ ($-1{,}000 \leq P_i \leq 1{,}000$).
Farmer John vuole trovare il massimo profitto totale ottenuto dalle mucche durante un qualsiasi periodo consecutivo. (Nota che un periodo consecutivo può durare da un giorno a $N$ giorni.) Aiutalo scrivendo un programma che calcoli la massima somma di profitti consecutivi.
Input
Leggi i dati dallo standard input.
- Riga 1: un solo intero, $N$.
- Righe $2..N+1$: la riga $i+1$ contiene un solo intero, $P_i$.
Output
Scrivi il risultato sullo standard output.
- Riga 1: un solo intero che rappresenta la massima somma di profitti in un qualsiasi periodo consecutivo.
Esempi
Input 1
7 -3 4 9 -2 -5 8 -3
Output 1
14
Nota
La somma massima si ottiene sommando dal secondo al sesto numero (4, 9, -2, -5, 8), ottenendo 14.
Autore del problema: Neal Wu, 2007