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
[[3,1,9,2]][[-4,-1]][[5]][[]][[2,2]][[7,-7]]
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.