Sous-séquence de somme maximale
D'après 2021, Métropole, Candidats libres, J2, Ex. 5
Étant donné un tableau non vide de nombres entiers relatifs, on appelle sous-séquence une suite non vide d'éléments voisins de ce tableau. On cherche dans cet exercice à déterminer la plus grande somme possible obtenue en additionnant les éléments d'une sous-séquence.
Par exemple, pour le tableau ci-dessous, la somme maximale vaut 18. Elle est obtenue en additionnant les éléments de la sous-séquence en bleu ci- dessous (6 ; 8 ; -6 ; 10).
- 8 | - 4 | 6 | 8 | - 6 | 10 | - 4 | - 4 |
1.a. Quelle est la solution du problème si les éléments du tableau sont tous positifs ?
Réponse
Si tous les éléments sont positifs la somme est maximale lorsqu'ils sont tous additionnés. La solution est donc l'ensemble du tableau.
1.b. Quelle est la solution du problème si tous les éléments sont négatifs ?
Réponse
Il faut à l'inverse additionner le moins de nombres possibles. La somme est maximale lorsque l'on n'additionne que la valeur maximale du tableau.
2. Dans cette question, on examine toutes les sous-séquences possibles.
2.a. Écrire le code Python d'une fonction somme_sous_sequence(lst, i, j)
qui prend en argument une liste lst
et deux entiers i
et j
et renvoie la somme de la sous-séquence délimitée par les indices i
et j
(inclus).
Réponse
def somme_sous_sequence(lst, i, j):
somme = 0
for indice in range(i, j + 1):
somme += lst[indice]
return somme
2.b. La fonction plus_grande_somme
ci-dessous permet de déterminer la plus grande des sommes obtenues en additionnant les éléments de toutes les sous-séquences possibles du tableau lst
.
🐍 Script Python | |
---|---|
1 2 3 4 5 6 7 8 9 |
|
Parmi les quatre choix suivants, quel est le nombre de comparaisons
effectuées par cette fonction si le tableau lst
passé en paramètre contient 10
éléments ?
- 10
- 55
- 100
- 1055
Réponse
On fait 10 comparaisons pour les sommes débutant à l'indice 0
, 9 pour celles commençant à l'indice 1
, 8 pour celles commençant à l'indice 2
etc... Cela fait en tout \(10+9+8+\dots+1=\frac{(10 + 1) \times 10}{2} = 55\) comparaisons.
2.c. Recopier et modifier la fonction plus_grande_somme
pour qu'elle renvoie un tuple contenant la somme maximale et les indices qui délimitent la sous-séquence correspondant à cette somme maximale.
Réponse
def plus_grande_somme(lst):
n = len(lst)
somme_max = lst[0]
i_max = 0
j_max = 0
for i in range(n):
for j in range(i, n):
s = somme_sous_sequence(lst, i, j)
if s > somme_max :
somme_max = s
i_max = i
j_max = j
return (somme_max, i_max, j_max)
3. On considère dans cette question une approche plus élaborée. Son principe
consiste, pour toutes les valeurs possibles de l'indice i
, à déterminer la somme
maximale S[i]
des sous-séquences qui se terminent à l'indice i
.
En désignant par lst[i]
l'élément de lst
d'indice i
, on peut vérifier que :
S[0] = lst[0]
;- Pour tout indice
i
≥ 1 :S[i] = lst[i]
siS[i - 1]
≤ 0 ;S[i] = lst[i] + S[i - 1]
siS[i - 1]
> 0.
3.a. Recopier et compléter le tableau ci-dessous avec les valeurs de S[i]
pour la liste considérée en exemple.
i |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
lst[i] |
-8 | -4 | 6 | 8 | -6 | 10 | -4 | -4 |
S[i] |
... | ... | ... | ... | ... | ... | ... | ... |
Réponse
On obtient le tableau suivant :
i |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
lst[i] |
-8 | -4 | 6 | 8 | -6 | 10 | -4 | -4 |
S[i]] |
-8 | -4 | 6 | 14 | 8 | 18 | 14 | 10 |
3.b. La solution au problème étant la plus grande valeur des S[i]
, on demande de compléter la fonction plus_grande_somme_dyn
ci-dessous, de sorte que la variable S
contienne la liste des valeurs S[i]
.
🐍 Script Python | |
---|---|
1 2 3 4 5 |
|
Réponse
def plus_grande_somme_dyn(lst):
sommes_max = [lst[0]]
for i in range(1, len(lst)):
if sommes_max[-1] <= 0:
sommes_max.append(lst[i])
else:
sommes_max.append(sommes_max[-1] + lst[i])
return max(sommes_max)
3.c. En quoi la solution obtenue par cette approche est-elle plus avantageuse que celle de la question 2.b. ?
Réponse
Cette méthode ne fait qu'un seul parcours de la liste, son coût est linéaire.