Sous-tableau de somme maximale
Étant donné un tableau de n entiers, il faut identifier un sous-tableau contigu dont la somme des valeurs est la plus grande possible.
Entrée
La première ligne de l’entrée contient un entier n – le nombre d’éléments du tableau (1 ≤ n ≤ ).
La ligne suivante contient n entiers séparés par un espace, représentant les éléments du tableau ().
Sortie
Le programme doit afficher un seul entier – la somme la plus élevée que l’on puisse obtenir parmi tous les sous-tableaux possibles du tableau.
Exemples
Entrée | Sortie |
|---|---|
9 | 7 |
10 | 12 |
Explication
-2 1 -3
4 -1 3 1-4 -2 → La somme du sous-tableau en surbrillance est (4 - 1 + 3 + 1) = 71 -2
3 4 -3 1 7-10 -20 4 → La somme de ce sous-tableau est (3 + 4 - 3 + 1 + 7) = 12
Pouvez-vous rendre cela encore meilleur 😎 ?
Il est possible de résoudre ce problème sans employer de tableaux supplémentaires. Seriez-vous capable de procéder ainsi ?
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB