Premier plus long sous-tableau croissant — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 12)

Premier plus long sous-tableau croissant

Recherche séquentielle, dichotomique, arrière · niveau 3 (difficile)

Énoncé

On veut les indices $d$ et $f$ du premier plus long sous-tableau croissant (au sens large) $T [d : f]$ de $T [0 : n]$ , en $Θ (n)$ . Par exemple, pour $T = [3, 2, 1, 1, 2, 4, 1, 2, 2, 4]$ : $d = 2$ et $f = 6$ . On se donne l'invariant $I (d, f, j, k)$ : « $T [d : f]$ et $T [j : k]$ sont respectivement le premier plus long sous-tableau croissant et le plus long suffixe croissant de $T [0 : k]$ ».

Initialisation : donner des valeurs des variables qui rendent $I (d, f, j, k)$ vrai.
Progression : comment rétablir l'invariant après $k \leftarrow k + 1$ ?
Écrire la fonction int[] pplstc(int[] T) commentée par son invariant, et justifier sa complexité.

Corrigé

Pour $d = f = j = k = 0$ , les trois sous-tableaux sont vides et $I (0, 0, 0, 0)$ est vrai.
On ajoute la case $k$ au préfixe. Le plus long suffixe croissant de $T [0 : k + 1]$ prolonge celui de $T [0 : k]$ si $k = 0$ ou $T [k - 1] \leq T [k]$ ; sinon il repart de $k$ :

$I (d, f, j, k) et k \neq = n et k > 0 et T [k - 1] > T [k] \Rightarrow I (d, f, k, k) .$

Après $k \leftarrow k + 1$ , $T [j : k]$ est le plus long suffixe croissant du nouveau préfixe. S'il est strictement plus long que $T [d : f]$ , il devient le premier plus long sous-tableau croissant ; en cas d'égalité, on garde le premier. -


static int[] pplstc(int[] T) { int n = T.length;
    int d = 0, f = 0, j = 0, k = 0;
    // I(d,f,j,k) : T[d:f] est le pplstc de T[0:k]
    //              et T[j:k] son plus long suffixe croissant
    while (k != n) {
        if (k > 0 && T[k - 1] > T[k]) j = k;  // le suffixe repart de k
        k = k + 1;                             // T[j:k] : suffixe de T[0:k]
        if (k - j > f - d) { d = j; f = k; }   // strictement plus long
    }
    // I(d,f,j,n) : T[d:f] est le pplstc de T
    return new int[] {d, f};
}


[3, 2, 1, 1, 2, 4, 1, 2, 2, 4] -> d=2 f=6 [1, 1, 2, 4]
[] -> d=0 f=0 []
[3, 2, 1] -> d=0 f=1 [3]
[1, 2, 0, 1, 2, 0, 1] -> d=2 f=5 [0, 1, 2]


nom : T
valeurs : 3 2 1 1 2 4 1 2 2 4
vert : 2..5
colorier : 6..9
pointeurs : d=2 f=6 j=6 k=n
zone : 2..5 T[d:f]
zone : 6..9 T[j:k]
legende : k = n : T[j:k] a la même longueur 4, on garde le premier

Le corps de boucle est en temps constant et s'exécute $n$ fois ( $n - k$ décroît de $1$ à chaque tour) : $Θ (n)$ .