Sous-tableau maximal avec l’algorithme de Kadane
À chaque position, Kadane choisit de continuer ou de recommencer.
Qu’est-ce que Sous-tableau maximal avec l’algorithme de Kadane ?
À chaque position, Kadane choisit de continuer ou de recommencer.
Trouver la plage contiguë dont la somme est maximale.
Quand l’utiliser ?
- Comprendre les algorithmes et structures de données.
- Observer chaque étape et traiter les cas limites.
- Comparer temps d’exécution et mémoire.
Code d’exemple
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]))Résultat attendu
6Fonctionnement
Un passage suffit : temps O(n), mémoire O(1).
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices pratiques
Modifiez les entrées et testez les cas limites avant d’utiliser des données plus volumineuses.
- Testez une entrée vide, un élément et des doublons.
- Affichez l’état après chaque étape.
- Comparez les performances avec une autre solution.