Le Monde des toons – Épreuve régionale 2012

Niveau 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

Contraintes d'exécution

Utilisation mémoire maximum
15000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
5
3 7 -4 1 2
Exemple de sortie
10
Exemple d'entrée
6
2 -3 7 -4 3 3
Exemple de sortie
9