Accueil › Coding & algorithmique › La meilleure semaine
La meilleure semaine
Exercice de la série « Tableaux et parcours »intermediaire
Le problème. Des mesures journalières, et une fenêtre de k jours
consécutifs. On veut le meilleur cumul sur une telle fenêtre.
Écrivez meilleureFenetre(mesures, k) qui le renvoie, ou null si k
est nul, négatif, ou plus grand que le nombre de mesures.
| Appel | Résultat attendu |
|---|---|
meilleureFenetre([2, 1, 5, 1, 3, 2], 3) |
9 — les jours 5, 1, 3 |
meilleureFenetre([1, 2, 3], 2) |
5 — la dernière fenêtre |
meilleureFenetre([-1, -2, -3], 2) |
-3 |
meilleureFenetre([1, 2], 3) |
null |
meilleureFenetre([5, 5, 5], 0) |
null |
Ce qu'on attend. À chaque pas, un jour entre et un jour sort : la mise à jour du cumul est en O(1), donc le tout en O(n). Resommer chaque fenêtre donnerait O(n × k).
Le piège. La borne de la boucle. La dernière fenêtre commence à
l'index n - k, et c'est souvent celle qu'on oublie de tester.
Cas de test
[[2,1,5,1,3,2],3][[1,2,3],2][[-1,-2,-3],2][[1,2],3][[5,5,5],0][[],1]
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.