Sous-tableau à somme maximale avec l’algorithme Diviser pour Régner
Étant donné un tableau de
n entiers, il s’agit de trouver un sous-tableau contigu dont la somme des valeurs est maximale en utilisant la technique de diviser pour régner.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 et représentant les éléments du tableau .Sortie
Le programme doit afficher un entier unique – la somme la plus élevée possible parmi tous les sous-tableaux du tableau donné.
Exemples
Entrée | Sortie |
9
-2 1 -3 4 -1 3 1 -4 -2 | 7 |
10
1 -2 3 4 -3 1 7 -10 -20 4 | 12 |
Explication
- -2 1 -3
4 -1 3 1-4 -2 → La somme du sous-tableau mis en évidence est (4 - 1 + 3 + 1) = 7
- 1 -2
3 4 -3 1 7-10 -20 4 → 3 + 4 -3 + 1 + 7 = 12
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB