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.
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.