Probleme – La plus longue sous-suite croissante, de $\Theta (n^2)$ à $\Theta (n\log n)$

1. La version dynamique. Sous-problème : $L[i]$ est la longueur de la plus longue sous-suite strictement croissante se terminant en $a_i$. Le « se terminant en » est l'idée de tout le problème : sans lui, on ne sait pas recoller.

$$L[i]=1+\max (\{0\}\cup \{L[j]\mid j<i\text{et}{a}_j<a_i\}).$$

(* Longueur de la plus longue sous-suite strictement croissante.
   Complexite : Theta(n^2) en temps, Theta(n) en memoire. *)
let lis_quadratique a =
  let n = Array.length a in
  let l = Array.make n 1 in
  for i = 0 to n - 1 do
    (* INVARIANT : pour tout k < i, l.(k) est la longueur maximale
       d'une sous-suite croissante se terminant en a.(k). *)
    for j = 0 to i - 1 do
      if a.(j) < a.(i) && l.(j) + 1 > l.(i) then l.(i) <- l.(j) + 1
    done
  done;
  Array.fold_left max 0 l

La réponse est le maximum des $L[i]$, et non $L[n-1]$ : la plus longue sous-suite ne finit pas nécessairement au dernier élément. C'est la faute classique de l'exercice.

2. La version en $\Theta (n\log n)$. On maintient un tableau $q$ où $q[k]$ est la plus petite valeur qui puisse terminer une sous-suite croissante de longueur $k+1$ parmi les éléments déjà lus. Ce tableau est strictement croissant — c'est ce qui autorise la dichotomie.

(* Meme specification, en Theta(n log n). *)
let lis_nlogn a =
  let n = Array.length a in
  let q = Array.make n 0 in
  let taille = ref 0 in
  Array.iter (fun x ->
    (* premier indice k tel que q.(k) >= x, par dichotomie *)
    let g = ref 0 and d = ref !taille in
    while !g < !d do
      let mi = (!g + !d) / 2 in
      if q.(mi) < x then g := mi + 1 else d := mi
    done;
    q.(!g) <- x;                       (* on ecrase, ou on allonge *)
    if !g = !taille then incr taille) a;
  !taille

Pourquoi $q$ reste croissant. On remplace $q[k]$ par $x$ seulement si $q[k]\ge x$ (c'est le premier tel indice) et $q[k-1]<x$ : la valeur baisse à sa place, l'ordre est préservé. Et taille ne croît que d'une unité à la fois, quand $x$ dépasse toutes les queues connues.

Mesure, les deux versions sur les mêmes entrées :

a = [3;1;4;1;5;9;2;6;5;3;5;8;9;7;9]   quadratique = 6   n log n = 6
b = [2;5;3;4;1]                        quadratique = 3   n log n = 3
c = [10;9;2;5;3;7;101;18]              quadratique = 4   n log n = 4

3. Non, et c'est le piège. Sur $b=[2;5;3;4;1]$, le tableau $q$ vaut à la fin $[1;3;4]$. Or $1$ apparaît après $3$ et $4$ dans $b$ : $[1;3;4]$ n'est pas une sous-suite de $b$. Sa longueur, $3$, est pourtant la bonne — une plus longue sous-suite croissante est $[2;3;4]$.

Ce qu'il faut en retenir : $q$ n'est pas une solution, c'est un certificat de longueur. Pour rendre le mot, il faut mémoriser, pour chaque élément inséré, l'indice de son prédécesseur dans $q$ au moment de l'insertion, puis remonter — exactement le procédé de reconstruction du chapitre, appliqué à une table qui n'a pas la forme d'une table. Un algorithme rapide qui rend la bonne valeur ne rend pas pour autant la solution, et c'est vrai bien au-delà de cet exemple.