CodeUtility
Faciliter la vie des développeurs !
Algorithmes Python

Maximum Subarray Sum with Kadane's Algorithm in Python

Find the run of numbers with the largest sum in one pass, even when the list has negative values.

  • Intermédiaire
  • 2 min de lecture
  • 1 exemple exécutable
Ce que vous allez apprendre
  • The best sum ending at each position
  • Starting fresh when the running sum hurts
  • O(n) time and O(1) memory
Exécuter dans le compilateur Python →
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
-2
1
-3
4
-1
2
1
-5
4
4 - 1 + 2 + 1 = 6 is the largest sum of any contiguous run.

Extend the run or start again

Le problème du sous-tableau de somme maximale (maximum subarray) consiste à trouver la portion d'éléments consécutifs dont la somme est la plus grande dans une liste contenant des nombres positifs et négatifs. L'algorithme de Kadane le résout très efficacement en retenant la meilleure somme de la portion qui se termine à la position courante.

Points clés

  1. current = max(value, current + value): keep the run only if it helps.
  2. best = max(best, current) remembers the best run so far.
  3. Start both from the first value so all-negative lists work.

Quand l’utiliser ?

  • Développer votre raisonnement et comprendre étape par étape le fonctionnement d’un algorithme.
  • Choisir la bonne approche quand il faut traiter beaucoup de données ou accélérer un programme.
  • Vous préparer aux examens, aux exercices et aux entretiens de programmation.

Code d’exemple

Exécuter le code →
main.py
def maximum_subarray_sum(values):
    current = best = values[0]
    for value in values[1:]:
        current = max(value, current + value)
        best = max(best, current)
    return best

print(maximum_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
Obtenir un bouton Run pour cet exemple

Résultat de l’exécution

6

Explication du code

Pour chaque élément, la variable current choisit entre deux options : démarrer une nouvelle portion à partir de cet élément, ou prolonger la portion précédente avec current + value. La variable best garde la plus grande somme rencontrée. Avec les données d'exemple, la portion [4, -1, 2, 1] donne la somme maximale, 6. L'algorithme s'exécute en O(n) et n'utilise que O(1) mémoire.

Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.

Exercices d’approfondissement

Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis