Le Monde des toons – Regional event 2012

Level 3

Énoncé

Vous partez en vacances, et souhaitez emporter des DVD des Looney Tunes®. Pris par le temps, vous ne pourrez qu'en tirer une pile de DVD consécutifs.

À partir de votre appréciation (positive ou négative) de chaque DVD, vous devez déterminer la meilleure pile de DVD consécutifs à choisir, c'est-à-dire celle réalisant la somme maximale. Si toutes vos appréciations sont négatives, vous pouvez n'en prendre aucun.

Entrée

  • Sur la première ligne, le nombre N de DVD.
  • Sur la ligne suivante, les N entiers représentant votre appréciation pour chaque DVD.

Sortie

  • La valeur de la somme maximale des appréciations.

Contraintes

  • 1 <= L <= 500 000
  • -10 000 <= Ai <= 10 000

Runtime constraints

Maximum memory usage
15000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
5
3 7 -4 1 2
Sample output
10
Sample input
6
2 -3 7 -4 3 3
Sample output
9

Submit your solution

You have to register or log in to be able to submit your solution.