Najdłuższy podciąg rosnący (LIS)

Wybieraj liczby z listy, od lewej do prawej, każdą większą od poprzedniej. Jak długi może być taki łańcuch? Pytanie jest na tyle proste, że pasuje do książki z łamigłówkami, a odpowiedź łączy grę w karty, klasyczną tabelę programowania dynamicznego i jeden z najpiękniejszych wyników dotyczących losowego tasowania.

Rząd słupków o różnej wysokości, z których rosnący łańcuch od lewej do prawej jest wyróżniony na pomarańczowo
Rząd słupków o różnej wysokości, z których rosnący łańcuch od lewej do prawej jest wyróżniony na pomarańczowo

Problem

Dla danej listy liczb podciąg zachowuje niektóre z nich w ich pierwotnej kolejności. Jest rosnący, jeśli każda wartość jest większa od poprzedniej. Najdłuższy podciąg rosnący, czyli LIS, to najdłuższy taki wybór. Lista n wartości ma 2ⁿ podciągów, więc sprawdzenie wszystkich działa tylko dla bardzo krótkich list.

Tabela

Niech len[i] oznacza długość najdłuższego podciągu rosnącego, który kończy się dokładnie na pozycji i. Wynosi ona 1 dla samej wartości albo 1 + len[j] dla wcześniejszej pozycji j o mniejszej wartości, zależnie od tego, co jest największe. Każda pozycja patrzy wstecz na wszystkie wcześniejsze, więc tabela wymaga n·(n − 1)/2 porównań. Odpowiedzią jest największe len[i], a zapisanie, które j dało każde len[i], pozwala odczytać podciąg wstecz.

Przykład

Weź 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. Pozycja po pozycji długości wynoszą 1, 2, 1, 1, 3, 2, 3, 4, 3 i 5: 20 przedłuża 3, 10; 4 przedłuża 3; 6 przedłuża 4, 7 przedłuża 6, a 9 przedłuża 7. Odczyt wstecz od 9 daje 3, 4, 6, 7, 9, podciąg rosnący o długości 5.

Szybciej: sortowanie pasjansowe

Rozdawaj wartości jak karty na stosy: każda wartość trafia na stos najbardziej z lewej, którego wierzch nie jest od niej mniejszy, albo zaczyna nowy stos po prawej. Liczba stosów to długość LIS. Ponieważ wierzchy stosów są zawsze posortowane, właściwy stos można znaleźć wyszukiwaniem binarnym, więc cała metoda zajmuje O(n log n) kroków. Nazwa pochodzi od pasjansa, którego przypomina.

Trochę matematyki

W 1935 roku Paul Erdős i George Szekeres udowodnili, że każda lista n² + 1 różnych liczb ma podciąg rosnący lub malejący o długości n + 1. Stanislaw Ulam zapytał w 1961 roku, jak długi jest LIS losowej permutacji n liczb. Odpowiedź, bliską 2√n dla dużych n, ustalili w 1977 roku Anatoly Vershik i Sergei Kerov oraz Ben Logan i Larry Shepp, a w 1999 roku Jinho Baik, Percy Deift i Kurt Johansson znaleźli dokładny kształt jej wahań: rozkład Tracy–Widom z teorii macierzy losowych.

Paul Erdős na seminarium studenckim w Budapeszcie w 1992 roku. W 1935 roku wraz z George’em Szekeresem udowodnił, że każda lista n² + 1 różnych liczb ma rosnący lub malejący podciąg długości n + 1.
Paul Erdős na seminarium studenckim w Budapeszcie w 1992 roku. W 1935 roku wraz z George’em Szekeresem udowodnił, że każda lista n² + 1 różnych liczb ma rosnący lub malejący podciąg długości n + 1.
Portret Stanisława Ulama
Portret Stanisława Ulama

Sprawdź sam

Otwórz aplikację i naciśnij Krok. Pomarańczowa kolumna to pozycja, która jest właśnie obliczana, a niebieska kolumna to wcześniejsza pozycja, z którą jest porównywana. Wiersz Długość rośnie, gdy znajdowane są dłuższe łańcuchy, wiersz Następuje po pamięta, skąd się wzięły, a na końcu odpowiedź jest odczytywana wstecz na pomarańczowo i pokazywana pod tabelą.

Często zadawane pytania

Jaka jest złożoność czasowa LIS?

O(n²) z tabelą, bo każda pozycja patrzy na wszystkie wcześniejsze, oraz O(n log n) z sortowaniem pasjansowym i wyszukiwaniem binarnym. Obie metody potrzebują O(n) pamięci.

Jak znaleźć najdłuższy podciąg niemalejący?

Pozwól wartości następować po równej sobie: porównuj za pomocą ≤ zamiast <. W aplikacji zaznacz Zezwalaj na równe wartości. W sortowaniu pasjansowym kładź każdą wartość na stosie najbardziej z lewej, którego wierzch jest ściśle większy.

Czym jest najdłuższy podciąg malejący?

To ten sam problem z odwróconym porównaniem albo LIS listy, w której każdą wartość zastąpiono liczbą przeciwną. Według twierdzenia Erdősa–Szekeresa wystarczająco długa lista zawsze ma długi podciąg rosnący albo długi podciąg malejący.

Jak długi jest LIS losowej listy?

Dla losowej permutacji n różnych liczb bliski 2√n dla dużych n. Poprawka rośnie jak pierwiastek szóstego stopnia z n, więc dla tysiąca liczb średnia wynosi około 58, trochę mniej niż 2√1000 ≈ 63.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj najdłuższy podciąg rosnący