Plus longue sous-séquence croissante en $\Theta (n\log n)$

• Soit $k<k^{\prime }$ et une sous-séquence croissante de longueur $k^{\prime }+1$ finissant par $F[k^{\prime }]$. Ses $k+1$ premiers éléments forment une sous-séquence croissante de longueur $k+1$ dont le dernier élément est strictement inférieur à $F[k^{\prime }]$. Donc $F[k]<F[k^{\prime }]$.
• Soit $x=s_j$ et $g$ le premier indice tel que $F[g]\ge x$ (ou $g=r$, le nombre de cases utiles, si $x$ dépasse tout). Les séquences de longueur $g$ finissent par $F[g-1]<x$ : $x$ les prolonge en une séquence de longueur $g+1$ finissant par $x\le F[g]$. On pose donc $F[g]=x$, et $r$ augmente de $1$ si $g=r$. Comme $F$ est croissant, $g$ se trouve par dichotomie.
• Programme :

static int longueurPlssc(int[] S) {
    int[] F = new int[S.length];
    int r = 0;                                   // F[0:r] strictement croissant
    for (int x : S) {
        int g = 0, d = r;
        while (g < d) {                          // F[0:g] < x <= F[d:r]
            int m = (g + d) / 2;
            if (F[m] < x) g = m + 1; else d = m;
        }
        F[g] = x;                                // x prolonge une séquence de longueur g
        if (g == r) r++;
    }
    return r;
}

Évolution de $F$ sur l'exemple : $[6]$, $[5]$, $[1]$, $[1,2]$, …, $[1,2,3,4,5]$, puis $7$ l'allonge, $6$ remplace $7$, $8$ l'allonge : $[1,2,3,4,5,6,8]$, de longueur $7$. Les deux derniers éléments donnent $[0,1,3,4,5,6,8]$ : $F$ n'est pas une sous-séquence de $S$, seule sa longueur compte. Chacun des $n$ éléments coûte une dichotomie en $\Theta (\log n)$ : $\Theta (n\log n)$, contre $\Theta (n^2)$ pour la version du cours.

nom : S
valeurs : 6 5 1 2 3 4 5 2 7 6 8 0 1
vert : 2..6 9 10
legende : une plssc de longueur 7 : 1 2 3 4 5 6 8

nom : F
valeurs : 0 1 3 4 5 6 8
colorier : 0 1
legende : F à la fin : 0 et 1 ont remplacé 1 et 2, F ne se lit plus dans S