Plus long plateau

On suit exactement le schéma du pplstc, en remplaçant « croissant » par « plateau ». Invariant $I(d,f,j,k)$ : « $T[d:f]$ est le premier plus long plateau du $k$-préfixe de $T$, et $T[j:k]$ son plus long suffixe plateau » (sous-tableaux vides si $k=0$).

• Initialisation : $I(0,0,0,0)$.
• Progression :

$$\begin{array}{l}I\wedge k\ne n\wedge (k=0\vee T[k-1]=T[k])\wedge k+1-j>f-d\Rightarrow I(j,k+1,j,k+1)\\ I\wedge k\ne n\wedge (k=0\vee T[k-1]=T[k])\wedge k+1-j\le f-d\Rightarrow I(d,f,j,k+1)\\ I\wedge k\ne n\wedge k>0\wedge T[k-1]\ne T[k]\Rightarrow I(d,f,k,k+1)\end{array}$$

• Arrêt : $k=n$ ; $T[d:f]$ est le premier plus long plateau de $T$.

static int[] plateau(int[] T) { int n = T.length;
    // I(d,f,j,k) : T[d:f] premier plus long plateau et
    //              T[j:k] plus long suffixe plateau du k-préfixe
    int d = 0, f = 0, j = 0, k = 0;   // I(0,0,0,0)
    while (k != n) {                  // I(d,f,j,k) et k ≠ n
        if (k > 0 && T[k-1] != T[k]) j = k;   // le suffixe plateau repart de k
        k = k + 1;                    // T[j:k] plus long suffixe plateau
        if (k - j > f - d) { d = j; f = k; }  // I(d,f,j,k)
    }                                 // I(d,f,j,n)
    return new int[] {d, f};
}

Sur l'exemple, la fonction retourne $[2,5]$ : le plateau $[1,1,1]$, et non $[2,2,2]$ qui est aussi long mais vient après. Boucle de $n$ tours en temps constant : $\Theta (n)$.

nom : T
valeurs : 5 5 1 1 1 7 2 2 2 9
vert : 2..4
colorier : 6..8
pointeurs : d=2 f=5 j=6 k=9
zone : 2..4 T[d:f]
zone : 6..8 T[j:k]
legende : k = 9 : T[j:k] est aussi long que T[d:f], on garde le premier