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
🐍 Script Python
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
def plus_grande_somme(lst):
    n = len(lst)
    somme_max = lst[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
    return somme_max

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
🐍 Script Python
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] si S[i - 1] ≤ 0 ;
    • S[i] = lst[i] + S[i - 1] si S[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
def plus_grande_somme_dyn(lst):
    sommes_max = [lst[0]]
    for i in range(1, len(lst)):
        # à compléter
    return max(sommes_max)
Réponse
🐍 Script Python
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.