Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Du quadratique au linéaire

Du quadratique au linéaire

Exercice de la série « Complexité, structures et cas limites »intermediaire

Le problème. Sur une série de relevés, on veut l'écart maximal entre deux valeurs : la plus grande moins la plus petite.

Écrivez ecartMaximal(releves) qui renvoie cet écart, et 0 si la série compte moins de deux valeurs.

Appel Résultat attendu
ecartMaximal([3, 1, 9, 2]) 8
ecartMaximal([-4, -1]) 3
ecartMaximal([5]) 0
ecartMaximal([]) 0
ecartMaximal([2, 2]) 0

Ce qu'on attend. La réponse naïve compare toutes les paires : O(n²). L'écart maximal ne dépend que de deux valeurs — lesquelles ? Un seul parcours doit suffire, donc O(n).

Cas de test

Écrire le code et le faire exécuter →

Votre code s'exécute réellement dans le navigateur, et la correction compare son résultat à celui d'une solution de référence.

La leçon qui prépare cet exercice

Les autres exercices de « Complexité, structures et cas limites »