Algorithmes avancés pour problèmes de programmation compétitive
A. Sous-tableau maximum à deux segments
Algorithme standard du sous-tableau maximum :
for (int idx = 1; idx <= n; idx++)
cumul[idx] = max(cumul[idx - 1] + valeurs[idx], valeurs[idx]);
cumul[i] représente la somme maximale se terminant à la position i, calculée à partir de la valeur précédente ou en recommençant une nouvelle séquence.
S ...
Publié le 8 juillet à 20h47