Où s'arrêter ?

Le tableau $M$ contient déjà, pour chaque case $j$, la valeur maximum d'un chemin de $0$ à $j$. La valeur cherchée est donc ${\max }_{0\le j<n}m(j)$, obtenue par un parcours de $M$ en $\Theta (n)$ ; si $j^{\star }$ est un indice où ce maximum est atteint, l'appel acm(M, R, jstar) affiche le chemin. Sur le ruban du cours, $M=[1,-\infty ,2,0,-18,-28,20]$ : le maximum est encore atteint en $j^{\star }=6$, valeur $20$. Sur le ruban $[3,5,-4,1,-9]$, en revanche, $M=[3,-\infty ,-1,4,-10]$ et Zébulon a intérêt à s'arrêter en case $3$ (valeur $4$) plutôt que d'aller jusqu'au bout ($-10$).

nom : M
valeurs : 3 -∞ -1 4 -10
vert : 0
colorier : 3
fleches : 0->3
legende : ruban [3, 5, -4, 1, -9] : maximum de M en case 3, chemin 0 → 3