Cases remplies
Comparaisons
Plus longue jusqu'ici

  • En cours de remplissage
  • Lue
  • Réponse

En savoir plus sur la plus longue sous-suite croissante

Plus longue sous-suite croissante (LIS)

Dans une liste de nombres, combien pouvez-vous en choisir, en gardant leur ordre, pour que chacun soit plus grand que le précédent ? La plus longue sous-suite croissante répond à cette question. Saisissez une liste et regardez la programmation dynamique calculer, pour chaque position, la plus longue chaîne qui s'y termine. Appuyez sur Lecture pour voir le tableau se remplir, ou sur Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où. Saisissez une liste de nombres. Pour chaque position, le tableau indique la longueur de la plus longue chaîne croissante de valeurs qui se termine là, et la position précédente qu'elle prolonge. Cochez Autoriser les valeurs égales pour des chaînes qui ne descendent jamais. À la fin, la chaîne est relue à partir de sa dernière valeur. Nouvel exemple crée une autre liste. Quand le plateau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.

Comment ça marche

  1. Saisissez une liste de nombres, séparés par des virgules ou des espaces. Cochez Autoriser les valeurs égales pour des chaînes qui ne descendent jamais.
  2. Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où.
  3. Regardez chaque position comparée à toutes les précédentes, puis voyez la plus longue chaîne relue en orange.

Comment fonctionne le tableau

Le tableau a trois lignes : les valeurs, la longueur de la plus longue sous-suite croissante qui se termine à chaque position, et la position qu'elle prolonge. Une valeur seule forme une chaîne de longueur 1. Ensuite, chaque position antérieure est examinée : si sa valeur est plus petite, la chaîne qui s'y termine peut être prolongée par cette valeur, ce qui donne une longueur de plus. Le prolongement le plus long l'emporte, et sa position va dans la troisième ligne.

Relire la chaîne

La plus longue sous-suite croissante se termine à la position qui a la plus grande longueur. À partir de là, la troisième ligne indique quelle position vient avant, puis la troisième ligne de cette position indique celle qui vient encore avant, jusqu'à une position sans prédécesseur. Lues dans l'ordre, ces valeurs forment la réponse. Avec Autoriser les valeurs égales coché, une valeur peut aussi suivre une valeur égale, ce qui donne la plus longue chaîne qui ne descend jamais.

Questions fréquemment posées

Quelle est la différence entre une sous-suite et un sous-tableau ?

Un sous-tableau est un bloc de valeurs voisines. Une sous-suite garde l'ordre mais peut sauter des valeurs : dans 3, 10, 2, 1, 20, les valeurs 3, 10 et 20 forment une sous-suite croissante, même si 2 et 1 se trouvent entre elles.

Quelle est la rapidité de l'algorithme LIS ?

La méthode du tableau compare chaque paire de positions : n·(n − 1)/2 comparaisons pour n valeurs. Le tri patience y parvient en O(n log n) : il retient, pour chaque longueur, la plus petite valeur qui termine une chaîne de cette longueur, et place chaque nouvelle valeur par recherche dichotomique.

La plus longue sous-suite croissante est-elle unique ?

Pas toujours. Dans 1, 3, 2, 4, les sous-suites 1, 3, 4 et 1, 2, 4 ont toutes deux la longueur 3. Le tableau donne la longueur, et la relecture en trouve une.

Où utilise-t-on la plus longue sous-suite croissante ?

Pour comparer des fichiers et des génomes, où certaines méthodes trouvent d'abord les lignes qui correspondent, puis prennent une sous-suite croissante de leurs positions ; dans des problèmes de planification et des casse-tête d'empilement de boîtes ; et en mathématiques, où la longueur de la LIS d'un mélange aléatoire est un objet d'étude célèbre.

Des données sont-elles envoyées quelque part ?

Non. Tout est calculé dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

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

Aller à l'éditeur