convertir une boucle Pour imbriquée en une boucle Pour simple

La technique de la fenêtre coulissante

La fenêtre coulissante (sliding window) est une technique algorithmique qui permet de traiter efficacement des sous-tableaux ou sous-chaînes consécutifs, en évitant les recalculs inutiles.

Sur un tableau [a, b, c, d, e, f, g, h], une fenêtre de taille 3 se déplace ainsi :

[a  b  c] d  e  f  g  h     → fenêtre 1
 a [b  c  d] e  f  g  h     → fenêtre 2  (+d, -a)
 a  b [c  d  e] f  g  h     → fenêtre 3  (+e, -b)
 a  b  c [d  e  f] g  h     → fenêtre 4  (+f, -c)
 a  b  c  d [e  f  g] h     → fenêtre 5  (+g, -d)
 a  b  c  d  e [f  g  h]    → fenêtre 6  (+h, -e)

Fenêtre de taille fixe

Problème — Somme maximale de k éléments consécutifs

Approche naïve — O(n × k)

La première idée consiste à calculer la somme de chaque bloc de k éléments par une double boucle. Pour chaque position de départ i, on additionne les k éléments suivants.

Exemple n°1 — Force brute avec double boucle

import sys

def somme_max_naive(tab, k):
    n = len(tab)
    assert n >= k, "k doit être ≤ à la taille du tableau"

    max_somme = -sys.maxsize - 1

    for i in range(n - k + 1):          # n - k + 1 fenêtres possibles
        somme_courante = 0
        for j in range(k):              # somme des k éléments
            somme_courante += tab[i + j]
        max_somme = max(somme_courante, max_somme)

    return max_somme


tab1 = [1, 4, 2, 10, 23, 3, 1, 0, 20]
tab2 = [100, 200, 300, 400]

print(f"tab1, k=4 → {somme_max_naive(tab1, 4)}")   # 39
print(f"tab2, k=2 → {somme_max_naive(tab2, 2)}")   # 700

tab1, k=4 → 39
tab2, k=2 → 700

Approche optimisée — Fenêtre coulissante O(n)

L'idée clé est de ne pas recalculer la somme depuis zéro à chaque étape. Quand la fenêtre avance d'une position, on soustrait l'élément sortant et on ajoute l'élément entrant.

tab = [5,  2,  -1,  0,  3]   k = 3

Étape 0 — initialisation  :  somme = 5 + 2 + (-1)  =  6   ← max = 6
Étape 1 — glisse d'un pas :  somme = 6 - 5 + 0     =  1   ← max = 6
Étape 2 — glisse d'un pas :  somme = 1 - 2 + 3     =  2   ← max = 6

Résultat : 6  (fenêtre [5, 2, -1])

Exemple n°2 — Fenêtre coulissante avec trace d'exécution

def somme_max_fenetre(tab, k):
    n = len(tab)
    assert n >= k, "k doit être ≤ à la taille du tableau"

    # ── Étape 1 : somme de la première fenêtre ──────────
    somme_courante = sum(tab[:k])
    max_somme      = somme_courante
    print(f"Fenêtre initiale  tab[0:{k}] = {tab[:k]} → somme = {somme_courante}")

    # ── Étape 2 : faire glisser la fenêtre ──────────────
    for i in range(k, n):
        sortant = tab[i - k]      # élément qui quitte la fenêtre
        entrant = tab[i]          # élément qui entre dans la fenêtre
        somme_courante += entrant - sortant
        max_somme = max(max_somme, somme_courante)
        fenetre = tab[i - k + 1 : i + 1]
        print(f"  +{entrant:3} / -{sortant:3}  →  fenêtre {fenetre}  somme = {somme_courante}")

    return max_somme


tab = [5, 2, -1, 0, 3]
k   = 3
resultat = somme_max_fenetre(tab, k)
print(f"\nSomme maximale (k={k}) : {resultat}")

Fenêtre initiale  tab[0:3] = [5, 2, -1] → somme = 6
  +  0 /  -5  →  fenêtre [2, -1, 0]  somme = 1
  +  3 /  -2  →  fenêtre [-1, 0, 3]  somme = 2

Somme maximale (k=3) : 6

Exemple n°3 — Validation sur les deux cas de l'énoncé

def somme_max_fenetre(tab, k):
    n = len(tab)
    assert n >= k
    somme_courante = sum(tab[:k])
    max_somme = somme_courante
    for i in range(k, n):
        somme_courante += tab[i] - tab[i - k]
        max_somme = max(max_somme, somme_courante)
    return max_somme


cas = [
    ([1, 4, 2, 10, 23, 3, 1, 0, 20], 4, 39),
    ([100, 200, 300, 400],            2, 700),
    ([5, 2, -1, 0, 3],                3, 6),
]

for tab, k, attendu in cas:
    res = somme_max_fenetre(tab, k)
    ok  = "✅" if res == attendu else "❌"
    print(f"{ok}  tab={tab}, k={k}  →  {res}  (attendu {attendu})")

✅  tab=[1, 4, 2, 10, 23, 3, 1, 0, 20], k=4  →  39  (attendu 39)
✅  tab=[100, 200, 300, 400], k=2          →  700  (attendu 700)
✅  tab=[5, 2, -1, 0, 3], k=3             →  6    (attendu 6)

Comparaison des deux approches

Autres applications

La technique se généralise à de nombreux problèmes. En voici quelques exemples classiques avec une fenêtre de taille fixe :

Exemple n°4 — Moyenne glissante et minimum glissant

def moyennes_glissantes(tab, k):
    """Retourne la liste des moyennes de chaque fenêtre de taille k."""
    n = len(tab)
    somme = sum(tab[:k])
    moyennes = [somme / k]
    for i in range(k, n):
        somme += tab[i] - tab[i - k]
        moyennes.append(somme / k)
    return moyennes


def min_glissant(tab, k):
    """Retourne le minimum de chaque fenêtre de taille k."""
    n = len(tab)
    return [min(tab[i:i + k]) for i in range(n - k + 1)]


tab = [3, 1, 4, 1, 5, 9, 2, 6]
k   = 3

print(f"Tableau        : {tab}")
print(f"Moyennes (k=3) : {[round(m, 2) for m in moyennes_glissantes(tab, k)]}")
print(f"Minimums (k=3) : {min_glissant(tab, k)}")

Tableau        : [3, 1, 4, 1, 5, 9, 2, 6]
Moyennes (k=3) : [2.67, 2.0, 3.33, 5.0, 5.33, 5.67]
Minimums (k=3) : [1, 1, 1, 1, 2, 2]

resultat = calcul(tab[:k])          # initialiser la première fenêtre
for i in range(k, n):
    resultat += tab[i] - tab[i - k]  # glisser : +entrant, -sortant
    max_res = max(max_res, resultat)  # mettre à jour le résultat