Algorithme de Kadane
Sous-tableau de somme maximale en O(n)
Enonce
Écrire sous_tableau_somme_max(T) qui renvoie la plus grande somme d'un sous-tableau contigu non vide de T.
Exemple : pour [-2, 1, -3, 4, -1, 2, 1, -5, 4] la réponse est 6 (sous-tableau [4, -1, 2, 1]).
⚠ Contrainte : complexité $O(n)$ temps, $O(1)$ espace. Tu peux supposer T non vide.
Signature attendue
def sous_tableau_somme_max(T: list) -> int:Exemples
sous_tableau_somme_max([-2, 1, -3, 4, -1, 2, 1, -5, 4])→6sous_tableau_somme_max([1, 2, 3, 4, 5])→15sous_tableau_somme_max([-1, -2, -3, -4])→-1 (tous negatifs)
📖 Rappel de cours
Étant donné un tableau d'entiers (éventuellement négatifs), on cherche la somme maximale d'un sous-tableau contigu non vide. La version naïve teste tous les couples $(i,j)$ en $O(n^2)$ ou $O(n^3)$ ; Kadane descend à $O(n)$ grâce à un invariant malin.
Idée clé :
On maintient somme_courante = somme maximale d'un sous-tableau qui se termine à l'indice $i$.
À l'étape $i+1$, deux choix :
- étendre le sous-tableau courant : somme_courante + T[i+1]
- recommencer à T[i+1] seul
On prend le max des deux. En parallèle, somme_max garde la meilleure somme jamais vue.
Complexité $O(n)$ temps, $O(1)$ espace. Bijou classique de programmation dynamique « en ligne ».
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Arbres Binaires — Parcours et Hauteur
- Arbre Binaire de Recherche (ABR)
- Tri par Tas (Heap Sort)
- Chemins dans une Grille
- Distance d'Édition (Levenshtein)
- Rendu de Monnaie (DP)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.