Le sous-tableau de somme maximale, version quadratique

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 3 — Boucles imbriquées et complexité quadratique

Énoncé

Écrire une fonction meilleure_tranche(t) de complexité $O (n^{2})$ renvoyant la somme maximale d'une tranche non vide $t [i .. j]$ ( $i \leq j$ ), sans recalculer les sommes partielles depuis le début à chaque étape.

Corrigé

L'astuce consiste à remarquer que la somme de la tranche $t [i .. j]$ est égale à la somme de $t [i .. j - 1]$ à laquelle on ajoute la valeur $t [j]$ . On accumule la somme dans une variable locale lors du parcours interne :

def meilleure_tranche(t: list) -> float:
    """Précondition : t est non vide."""
    meilleur = t[0]
    for i in range(len(t)):
        s = 0
        for j in range(i, len(t)):
            s += t[j] # s est la somme accumulée de t[i..j]
            if s > meilleur:
                meilleur = s
    return meilleur

assert meilleure_tranche([2, -8, 3, -2, 4, -10]) == 5 # tranche [3, -2, 4]
assert meilleure_tranche([-3, -1, -7]) == -1          # cas des valeurs toutes négatives

Cette accumulation permet de descendre le coût de $O (n^{3})$ (calcul naïf) à $O (n^{2})$ .

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.