Plus longue sous-suite croissante (LIS)

Choisissez des nombres dans une liste, de gauche à droite, chacun plus grand que le précédent. Quelle longueur peut atteindre une telle chaîne ? La question est assez simple pour un livre d'énigmes, et sa réponse relie un jeu de cartes, un tableau classique de programmation dynamique et l'un des plus beaux résultats sur les mélanges aléatoires.

Une rangée de barres de hauteurs différentes, dont une chaîne montante, de gauche à droite, est mise en évidence en orange
Une rangée de barres de hauteurs différentes, dont une chaîne montante, de gauche à droite, est mise en évidence en orange

Le problème

Étant donné une liste de nombres, une sous-suite en garde certains dans leur ordre d'origine. Elle est croissante si chaque valeur est plus grande que la précédente. La plus longue sous-suite croissante, ou LIS, est le plus long choix de ce type. Une liste de n valeurs a 2ⁿ sous-suites, donc les vérifier toutes ne fonctionne que pour des listes très courtes.

Le tableau

Soit len[i] la longueur de la plus longue sous-suite croissante qui se termine exactement à la position i. Elle vaut 1 pour la valeur seule, ou 1 + len[j] pour une position antérieure j dont la valeur est plus petite, en prenant la plus grande. Chaque position regarde toutes les précédentes, donc le tableau demande n·(n − 1)/2 comparaisons. La réponse est le plus grand len[i], et noter quel j a donné chaque len[i] permet de relire la sous-suite.

Un exemple

Prenez 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. Position par position, les longueurs sont 1, 2, 1, 1, 3, 2, 3, 4, 3 et 5 : le 20 prolonge 3, 10 ; le 4 prolonge le 3 ; le 6 prolonge le 4, le 7 le 6, et le 9 le 7. En relisant à partir du 9, on obtient 3, 4, 6, 7, 9, une sous-suite croissante de longueur 5.

Plus rapide : le tri patience

Distribuez les valeurs comme des cartes en piles : chaque valeur va sur la pile la plus à gauche dont le sommet n'est pas plus petit qu'elle, ou commence une nouvelle pile à droite. Le nombre de piles est la longueur de la LIS. Comme les sommets des piles sont toujours triés, la bonne pile se trouve par recherche dichotomique, et toute la méthode prend O(n log n) étapes. Elle doit son nom au jeu de patience (la réussite) auquel elle ressemble.

Un peu de mathématiques

En 1935, Paul Erdős et George Szekeres ont prouvé que toute liste de n² + 1 nombres différents contient une sous-suite croissante ou décroissante de longueur n + 1. En 1961, Stanislaw Ulam s'est demandé quelle est la longueur de la LIS d'un mélange aléatoire de n nombres. La réponse, proche de 2√n pour n grand, a été établie en 1977 par Anatoly Vershik et Sergei Kerov ainsi que par Ben Logan et Larry Shepp, et en 1999 Jinho Baik, Percy Deift et Kurt Johansson ont trouvé la forme exacte de ses fluctuations : la loi de Tracy–Widom, issue de la théorie des matrices aléatoires.

Paul Erdős lors d’un séminaire d’étudiants à Budapest en 1992. En 1935, George Szekeres et lui ont prouvé que toute liste de n² + 1 nombres distincts contient une sous-suite croissante ou décroissante de longueur n + 1.
Paul Erdős lors d’un séminaire d’étudiants à Budapest en 1992. En 1935, George Szekeres et lui ont prouvé que toute liste de n² + 1 nombres distincts contient une sous-suite croissante ou décroissante de longueur n + 1.
Portrait de Stanisław Ulam
Portrait de Stanisław Ulam

À vous de jouer

Ouvrez l'application et appuyez sur Étape. La colonne orange est la position en cours de calcul, et la colonne bleue la position antérieure à laquelle elle est comparée. La ligne Longueur grandit à mesure que des chaînes plus longues sont trouvées, la ligne Vient après retient d'où elles viennent, et à la fin la réponse est relue en orange et affichée sous le tableau.

Questions fréquemment posées

Quelle est la complexité en temps de la LIS ?

O(n²) avec le tableau, car chaque position regarde toutes les précédentes, et O(n log n) avec le tri patience et la recherche dichotomique. Les deux demandent O(n) de mémoire.

Comment trouver la plus longue sous-suite non décroissante ?

Autorisez une valeur à suivre une valeur égale : comparez avec ≤ au lieu de <. Dans l'application, cochez Autoriser les valeurs égales. Avec le tri patience, posez chaque valeur sur la pile la plus à gauche dont le sommet est strictement plus grand.

Qu'est-ce que la plus longue sous-suite décroissante ?

Le même problème avec la comparaison inversée, ou la LIS de la liste dont chaque valeur est remplacée par son opposé. D'après le théorème d'Erdős–Szekeres, une liste assez longue a toujours une longue sous-suite croissante ou une longue sous-suite décroissante.

Quelle est la longueur de la LIS d'une liste aléatoire ?

Pour un mélange aléatoire de n nombres différents, environ 2√n pour n grand. La correction croît comme la racine sixième de n, donc pour mille nombres la moyenne est d'environ 58, un peu moins que 2√1000 ≈ 63.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Essayer la plus longue sous-suite croissante