Voir la source de Plus longue sous-suite strictement croissante

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

== Description ==
L'entrée du problème est une suite finie ''x''{{sub|1}}, ..., ''x''{{sub|n}}. De façon formelle, l'objectif est de trouver une [[sous-suite]] strictement croissante <math>(x_{\varphi(i)})_{i \leq L}</math> de la suite <math>(x_i)_{i \leq n}</math>, <math>\varphi</math> étant une fonction strictement croissante ⟦1, ''L''⟧ → ⟦1, ''n''⟧, pour la plus grande longueur ''L'' possible<ref name="schensted">{{Article
| langue = en
| auteur = [[Craige Schensted]]
| titre = Longest increasing and decreasing subsequences
| périodique = [[Canadian Journal of Mathematics]]
| volume = 13| passage = 179-191
| année = 1961
| doi = 10.4153/CJM-1961-015-3| math reviews = 0121305
}}.</ref>.

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 ''{{lang|en|longest increasing subsequence}}''.

== Algorithme ==
L'algorithme de [[programmation dynamique]] suivant résout le problème de la plus longue sous-suite croissante en temps [[Comparaison asymptotique#Échelle de comparaison|quasi linéaire]] O(''n'' log ''n''). Il utilise seulement des [[Tableau (structure de données)|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 [[Invariant de boucle|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]<nowiki />], X[M[2]<nowiki />], ..., X[M[L]<nowiki />] 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]<nowiki />], X[M[2]<nowiki />], ..., X[M[L]<nowiki />] 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]<nowiki />] < 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]<nowiki />] :
       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]<nowiki />], puis en remontant dans le tableau P des prédécesseurs : l'avant-dernier élément est <nowiki>X[P[M[L]]]</nowiki>, l'antépénultième est <nowiki>X[P[P[M[L]]]]</nowiki>, 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éduction (complexité)|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<nowiki>]]</nowiki>, ..., A[T[m<nowiki>]]</nowiki>, alors S[i[1<nowiki>]]</nowiki>, ..., S[i[k<nowiki>]]</nowiki> 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<ref>{{Ouvrage|langue=en|auteur1=[[Dan Gusfield]]|titre=Algorithms on Strings, Trees, and Sequences|sous-titre=Computer Science and Computational Biology|éditeur=[[Cambridge University Press]]|année=1997|mois=mai|pages totales=534|passage=290-292|isbn=978-0-521-58519-4|lire en ligne=https://books.google.com/books?id=Ofw5w1yuD8kC&printsec=frontcover|titre chapitre=Refining Core String Edits and Alignments}}.</ref>.

== Plus longue sous-suite strictement croissante d'une permutation ==

=== Définition ===
On note par <math>\mathfrak{S}_n </math> le [[groupe symétrique]] de permutations de ⟦1, n⟧. Soit <math>\sigma \in \mathfrak{S}_n</math> une permutation, on identifie la plus longue suite croissante  de la permutation avec la plus longue sous suite croissante de <math>(\sigma(i))_{1\leq i \leq n} </math>  et soit <math>\ell(\sigma) </math> sa longueur. <math>\ell(\sigma) </math>  présente également le nombre de piles dans le [[:en:Patience_sorting|Patience sorting]]<ref>{{Lien web|titre=American Mathematical Society|url=http://www.ams.org/home/page/|doi=10.1090/s0273-0979-99-00796-x|consulté le=2018-01-17}}</ref>.

=== Théorème de Baik-Deift-Johansson<ref>{{Lien web|titre=American Mathematical Society|url=http://www.ams.org/home/page/|doi=10.1090/s0894-0347-99-00307-0|consulté le=2018-01-17}}</ref> ===
Soit <math>n </math> un entier non nul et  <math>\mathbb{P}_n </math> la [[mesure de Haar]] (probabilité uniforme) sur <math>\mathfrak{S}_n </math> alors  pour tout réel <math>s </math>

<math display="block">\lim_{n\to \infty} \mathbb{P}_n\left(\frac{\ell(\sigma)-2\sqrt{n}}{n^\frac 16}<s\right)=F_2(s)  </math>

ou <math>F_2 </math> est la fonction cumulative de [[:en:Tracy–Widom_distribution|la distribution de Tracy-widom]] pour <math>\beta=2 </math>.

== Notes et références ==
{{Traduction/Référence|en|Longest increasing subsequence|580842077|type=note}}
{{Références}}

== Voir aussi ==
* {{Ouvrage |auteur1= Dan Romik
|titre= The Surprising Mathematics of Longest Increasing Subsequences
|éditeur= Cambridge University Press
|année= 2015
|pages totales= 353
|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]].

{{Portail|informatique théorique|Probabilités et statistiques}}

[[Catégorie:Problème algorithmique]]