Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Parcours, accumulateurs et sommes préfixes

Parcours, accumulateurs et sommes préfixes

Tableaux et parcoursdebutant

La plupart des exercices sur tableaux se résolvent en un seul parcours, en maintenant la bonne information.

// Maximum : l'initialisation décide de la justesse
int max = t[0];
for (int i = 1; i < t.length; i++) max = Math.max(max, t[i]);

// Somme : passer en long si les valeurs sont grandes
long somme = 0;
for (int x : t) somme += x;

// Compter sous condition
int pairs = 0;
for (int x : t) if (x % 2 == 0) pairs++;

Les sommes préfixes transforment des requêtes répétées en O(1) :

int[] p = new int[t.length + 1];               // p[0] = 0
for (int i = 0; i < t.length; i++) p[i + 1] = p[i] + t[i];

int sommeIntervalle = p[j + 1] - p[i];         // somme de t[i..j], en O(1)

Kadane résout « la somme maximale d'un sous-tableau contigu » en O(n) :

int courant = t[0], meilleur = t[0];
for (int i = 1; i < t.length; i++) {
    courant  = Math.max(t[i], courant + t[i]);   // prolonger, ou repartir ici
    meilleur = Math.max(meilleur, courant);
}

Et une technique à garder en tête : parcourir à rebours quand chaque élément dépend de ce qui le suit.

Les termes à connaître

Accumulateur

Une variable qui porte le résultat partiel pendant le parcours : somme, maximum, compteur. Son initialisation est la décision la plus importante.

Somme préfixe

Un tableau où p[i] contient la somme des i premiers éléments. Il permet ensuite d'obtenir la somme de n'importe quel intervalle en O(1) : p[j+1] - p[i].

Parcours unique

Résoudre en un seul passage, en maintenant l'information nécessaire au fil du parcours. Le réflexe qui transforme beaucoup d'O(n²) en O(n).

Algorithme de Kadane

La somme maximale d'un sous-tableau contigu, en O(n) : à chaque position, on choisit entre prolonger la séquence en cours ou repartir de l'élément courant.

Parcours à rebours

Parcourir de la fin vers le début. Souvent la clé quand chaque élément dépend de ce qui le suit — produits à droite, prochain élément plus grand.

Arrays.fill / copyOf

Arrays.fill(t, v) initialise, Arrays.copyOf(t, n) copie et redimensionne, Arrays.copyOfRange(t, a, b) extrait. À connaître pour ne pas réécrire de boucles.

Lire l'explication détaillée et faire le quiz →

Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.