Somme maximale de termes consécutifs

On considère un tableau non vide de nombre entiers, positifs ou négatifs, et on souhaite déterminer la plus grande somme possible de ses éléments consécutifs.

Par exemple, dans le tableau [1, -2, 3, 10, -4, 7, 2, -5], la plus grande somme est 18 obtenue en additionnant les éléments 3, 10, -4, 7, 2.

Pour cela, on va résoudre le problème par programmation dynamique. Si on note tab le tableau considéré et i un indice dans ce tableau, on se ramène à un problème plus simple : déterminer la plus grande somme possible de ses éléments consécutifs se terminant à l’indice i.

Si on connait la plus grande somme possible de ses éléments consécutifs se terminant à l’indice i - 1, on peut déterminer la plus grande somme possible de ses éléments consécutifs se terminant à l’indice i :

soit on obtient une plus grande somme en ajoutant tab[i] à cette somme précédente ;
soit on commence une nouvelle somme à partir de tab[i].

Remarque : les sommes considérées contiennent toujours au moins un terme.

Exemples

🐍 Console Python

>>> somme_max([1, 2, 3, 4, 5])
15
>> somme_max([1, 2, -3, 4, 5])
9
>>> somme_max([1, 2, -2, 4, 5])
10
>>> somme_max([1, -2, 3, 10, -4, 7, 2, -5])
18

Compléter le code ci-dessous

Compléter la fonction somme_max ci-dessous qui réalise cet algorithme.

###

# Testsbksl-nlassert sommepy-undmax([1, 2, 3, 4, 5]) == 15bksl-nlassert sommepy-undmax([1, 2, -3, 4, 5]) == 9bksl-nlassert sommepy-undmax([1, 2, -2, 4, 5]) == 10bksl-nlassert sommepy-undmax([1, -2, 3, 10, -4, 7, 2, -5]) == 18bksl-nlbksl-nl# Autres testsbksl-nlvaleurs = [42] py-str 100bksl-nlassert sommepy-undmax(valeurs) == 42 py-str 100, "Erreur avec tableau constant"bksl-nlbksl-nlbksl-nl 5/5

def sommepy-undmax(tab):bksl-nl n = len(tab)bksl-nl sommespy-undmax = [0] py-str nbksl-nl sommespy-undmax[0] = tab[0]bksl-nl # on calcule la plus grande somme se terminant en ibksl-nl for i in range(1, n):bksl-nl if ... + ... > ...: bksl-nl sommespy-undmax[i] = ... bksl-nl else:bksl-nl sommespy-undmax[i] = ... bksl-nl # on en déduit la plus grande somme de celles-cibksl-nl maximum = 0bksl-nl for i in range(1, n):bksl-nl if ... > ...: bksl-nl maximum = ibksl-nlbksl-nl return sommespy-undmax[...]bksl-nlbksl-nl# Testsbksl-nlassert sommepy-undmax([1, 2, 3, 4, 5]) == 15bksl-nlassert sommepy-undmax([1, 2, -3, 4, 5]) == 9bksl-nlassert sommepy-undmax([1, 2, -2, 4, 5]) == 10bksl-nlassert sommepy-undmax([1, -2, 3, 10, -4, 7, 2, -5]) == 18bksl-nlbksl-nlbksl-nldef sommepy-undmax(tab):bksl-nl n = len(tab)bksl-nl sommespy-undmax = [0] py-str nbksl-nl sommespy-undmax[0] = tab[0]bksl-nl # on calcule la plus grande somme se terminant en ibksl-nl for i in range(1, n):bksl-nl if sommespy-undmax[i - 1] + tab[i] > tab[i]:bksl-nl sommespy-undmax[i] = sommespy-undmax[i - 1] + tab[i]bksl-nl else:bksl-nl sommespy-undmax[i] = tab[i]bksl-nl # on en déduit la plus grande somme de celles-cibksl-nl maximum = 0bksl-nl for i in range(1, n):bksl-nl if sommespy-undmax[i] > sommespy-undmax[maximum]:bksl-nl maximum = ibksl-nl return sommespy-undmax[maximum]bksl-nl bksl-nl