Le problème de la plus longue sous-séquence croissante est un problème classique en programmation compétitive. Il consiste à rechercher, à l’intérieur d’une liste de \(n\) éléments, un sous-ensemble d’éléments qui y apparaissent en ordre croissant.
Ce problème peut être résolu en temps \(\mathcal{O}(n \log n)\) avec une recherche binaire. C’est notamment à l’aide de cette solution qu’on peut résoudre le problème “Train Sorting” présenté lors du concours interne d’il y a deux semaines.
Le nombre à côté de chaque problème indique son niveau de difficulté selon Kattis.
“Alphabet”2.7 — Quel est le nombre minimum de caractères qu’il faut ajouter à une chaîne pour qu’elle contienne une sous-séquence égale à l’alphabet entier?
“Increasing Subsequence”4.2 — Parmi les sous-séquences strictement croissantes d’une séquence, trouvez la plus basse dans l’ordre lexicographique.
“Longest Increasing Subsequence”5.3 — Trouvez n’importe quelle plus longue sous-séquence strictement croissante dans des longues liste d’entiers.
“Nested Dolls”6.5 — En rangeant optimalement une collection de matriochkas les unes dans les autres, combien de poupées peut-on avoir au minimum à la fin?