Plus longue sous-suite strictement croissante

La recherche d'une plus longue sous-suite strictement croissante dans une suite finie est un problème classique en algorithmique. Ce problème peut être résolu en temps O(n log n) avec n la longueur de la suite.

Description

L'entrée du problème est une suite finie x₁, ..., x_n. De façon formelle, l'objectif est de trouver une sous-suite strictement croissante $(x_{\varphi (i)})_{i\leq L}$ de la suite $(x_{i})_{i\leq n}$, $\varphi$ étant une fonction strictement croissante ⟦1, L⟧ → ⟦1, n⟧, pour la plus grande longueur L possible.

Par exemple, la suite (6, 1, 4, 9, 5, 11) possède des sous-suites strictement croissantes de longueur 4, mais aucune de longueur 5. Une plus longue sous-suite strictement croissante est (1, 4, 9, 11), obtenue en prenant les éléments en position 2, 3, 4 et 6 de la suite initiale. En général, la solution n'est pas unique. Ici, une autre solution est (1, 4, 5, 11).

Ce problème est parfois désigné par l'acronyme LIS, pour longest increasing subsequence.

Algorithme

L'algorithme de programmation dynamique suivant résout le problème de la plus longue sous-suite croissante en temps quasi linéaire O(n log n). Il utilise seulement des tableaux et une fonction de recherche dichotomique. Il traite les éléments de la suite dans l'ordre, en gardant en mémoire la plus longue sous-suite strictement croissante trouvée jusqu'à présent et d'autres sous-suites plus courtes mais dont le dernier élément est plus petit (donc potentiellement plus faciles à compléter avec les éléments suivants). Les éléments de la suite sont notés X[1], X[2], ..., X[N]. Après avoir traité X[i], les invariants suivants sont vérifiés :

• M[j] contient une position k telle que X[k] soit la plus petite valeur possible du dernier élément d'une sous-suite strictement croissante de X[1], ..., X[i] ayant exactement j éléments.
• P[k] contient l'indice du prédécesseur de X[k] dans une plus longue sous-suite strictement croissante se terminant en position k.

L'algorithme conserve dans une variable L la longueur de la plus longue sous-suite strictement croissante trouvée.

À tout moment, la suite X[M[1]], X[M[2]], ..., X[M[L]] est croissante. En effet, s'il existe une sous-suite strictement croissante de longueur i>1 se terminant en position M[i], alors il existe une sous-suite strictement croissante de longueur i-1 se terminant par une valeur inférieure. Comme la suite est croissante, il est possible de faire une recherche dichotomique dans cette suite. Attention : en général, la suite d'indices M[1], M[2], ..., M[L] n'est pas croissante, donc X[M[1]], X[M[2]], ..., X[M[L]] n'est pas une sous-suite de X[1], ..., X[L] (donc pas une solution du problème).

Description de l'algorithme :

Entrée : X, un tableau indicé de 1 à n.
Sortie : L, longueur de la plus longue sous-suite strictement croissante de X.
         P, tableau de prédécesseurs permettant de reconstruire explicitement la suite.

P = tableau indicé de 1 à n
M = tableau indicé de 0 à n

L = 0
M[0] = 0
pour i = 1, 2, ..., n :
   par recherche dichotomique, trouver le plus grand entier j tel que 1 ≤ j ≤ L
     et X[M[j]] < X[i] ou définir j = 0 s'il n'en existe aucun.
   P[i] = M[j]
   si j == L ou X[i] < X[M[j + 1]] :
      M[j + 1] = i
      L = max(L, j + 1)

Les éléments de la sous-suite peuvent être calculés en partant du dernier élément X[M[L]], puis en remontant dans le tableau P des prédécesseurs : l'avant-dernier élément est X[P[M[L]]], l'antépénultième est X[P[P[M[L]]]], etc.

À chaque tour de boucle, l'opération la plus coûteuse est la recherche dichotomique, de complexité O(log n). Le temps total d'exécution de l'algorithme est donc O(n log n).

Liens avec la plus longue sous-séquence commune

Le problème de la plus longue sous-suite croissante est lié à celui de la plus longue sous-suite commune à deux suites, pour lequel il existe un algorithme de résolution par programmation dynamique de complexité quadratique : pourvu que l'alphabet sur lequel sont définies les chaînes soit muni d'une relation d'ordre, la plus longue sous-suite croissante d'une suite S est la plus longue sous-suite commune à S et T, où T est obtenue en triant S.

Inversement, le problème de la plus longue sous-suite commune à deux suites S[1], S[2], ..., S[n] et T[1], T[2], ..., T[m] peut être réduit au problème de la plus longue sous-suite croissante. Pour cela, on note A[x] la liste des indices des éléments de S valant x par ordre décroissant. Si i[1], i[2], ..., i[k] est une plus longue sous-suite strictement croissante de la suite obtenue en concaténant A[T[1]], ..., A[T[m]], alors S[i[1]], ..., S[i[k]] est une plus longue sous-suite commune à S et T. La taille de la suite obtenue par concaténation est au plus nm, mais seulement m si la première suite ne contient pas d'élément en double. Ainsi, la réduction donne une méthode de résolution du problème de la plus longue sous-suite commune relativement efficace dans des cas particuliers courants.

Plus longue sous-suite strictement croissante d'une permutation

Définition

On note par ${\mathfrak {S}}_{n}$ le groupe symétrique de permutations de ⟦1, n⟧. Soit $\sigma \in {\mathfrak {S}}_{n}$ une permutation, on identifie la plus longue suite croissante de la permutation avec la plus longue sous suite croissante de $(\sigma (i))_{1\leq i\leq n}$ et soit $\ell (\sigma )$ sa longueur. $\ell (\sigma )$ présente également le nombre de piles dans le Patience sorting.

Théorème de Baik-Deift-Johansson

Soit $n$ un entier non nul et $\mathbb {P} _{n}$ la mesure de Haar (probabilité uniforme) sur ${\mathfrak {S}}_{n}$ alors pour tout réel $s$

$$\lim _{n\to \infty }\mathbb {P} _{n}\left({\frac {\ell (\sigma )-2{\sqrt {n}}}{n^{\frac {1}{6}}}}<s\right)=F_{2}(s)$$

ou $F_{2}$ est la fonction cumulative de la distribution de Tracy-widom pour $\beta =2$.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Longest increasing subsequence » (voir la liste des auteurs).

Voir aussi

• Dan Romik, The Surprising Mathematics of Longest Increasing Subsequences, Cambridge University Press, 2015, 353 p. (ISBN 9781107428829).
• Plus longue sous-suite commune
• La plus longue sous-suite strictement décroissante, correspond au problème de la clique dans un graphe de permutation.