- Wypełniana
- Odczytywana
- Odpowiedź
Najdłuższy podciąg rosnący (LIS)
Ile liczb z listy możesz wybrać, zachowując ich kolejność, tak aby każda była większa od poprzedniej? Odpowiada na to najdłuższy podciąg rosnący. Wpisz listę i zobacz, jak programowanie dynamiczne wyznacza dla każdej pozycji najdłuższy łańcuch, który się na niej kończy. Naciśnij Odtwórz, aby zobaczyć, jak wypełnia się tabela, albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Wpisz listę liczb. Dla każdej pozycji tabela przechowuje długość najdłuższego rosnącego łańcucha wartości, który się tam kończy, oraz wcześniejszą pozycję, którą ten łańcuch przedłuża. Zaznacz Zezwalaj na równe wartości, aby szukać łańcuchów, które nigdy nie maleją. Na końcu łańcuch jest odczytywany wstecz od ostatniej wartości. Nowy przykład tworzy inną listę. Gdy plansza jest zaznaczona, strzałki przesuwają o krok, spacja odtwarza i wstrzymuje, a Home i End przeskakują na początek i na koniec.
Jak to działa
- Wpisz listę liczb oddzielonych przecinkami lub spacjami. Zaznacz Zezwalaj na równe wartości, aby szukać łańcuchów, które nigdy nie maleją.
- Naciśnij Odtwórz albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce.
- Zobacz, jak każda pozycja jest porównywana ze wszystkimi wcześniejszymi, a potem jak najdłuższy łańcuch jest odczytywany wstecz na pomarańczowo.
Jak działa tabela
Tabela ma trzy wiersze: wartości, długość najdłuższego podciągu rosnącego kończącego się na każdej pozycji i pozycję, którą ten podciąg przedłuża. Sama wartość to łańcuch o długości 1. Potem sprawdzana jest każda wcześniejsza pozycja: jeśli jej wartość jest mniejsza, łańcuch, który się tam kończy, można przedłużyć o tę wartość, co daje długość o jeden większą. Wygrywa najdłuższe takie przedłużenie, a jego pozycja trafia do trzeciego wiersza.
Odczytywanie łańcucha wstecz
Najdłuższy podciąg rosnący kończy się na pozycji o największej długości. Stamtąd trzeci wiersz mówi, która pozycja jest wcześniej, a trzeci wiersz tej pozycji mówi, która jest jeszcze wcześniej, aż do pozycji bez poprzednika. Odczytane po kolei, te wartości są odpowiedzią. Gdy zaznaczone jest Zezwalaj na równe wartości, wartość może też następować po równej sobie, co daje najdłuższy łańcuch, który nigdy nie maleje.
Często zadawane pytania
Czym różni się podciąg od podtablicy?
Podtablica to blok sąsiednich wartości. Podciąg zachowuje kolejność, ale może pomijać wartości, więc w 3, 10, 2, 1, 20 wartości 3, 10 i 20 tworzą podciąg rosnący, mimo że między nimi stoją 2 i 1.
Jak szybki jest algorytm LIS?
Metoda tabeli porównuje każdą parę pozycji: n·(n − 1)/2 porównań dla n wartości. Sortowanie pasjansowe robi to w O(n log n): pamięta dla każdej długości najmniejszą wartość kończącą łańcuch tej długości i umieszcza każdą nową wartość wyszukiwaniem binarnym.
Czy najdłuższy podciąg rosnący jest jednoznaczny?
Nie zawsze. W 1, 3, 2, 4 zarówno 1, 3, 4, jak i 1, 2, 4 mają długość 3. Tabela podaje długość, a odczyt wstecz znajduje jeden z nich.
Gdzie stosuje się najdłuższy podciąg rosnący?
Przy porównywaniu plików i genomów, gdzie niektóre metody najpierw znajdują pasujące wiersze, a potem biorą rosnący podciąg ich pozycji; w planowaniu i łamigłówkach z układaniem pudełek w stos; oraz w matematyce, gdzie długość LIS losowej permutacji jest słynnym obiektem badań.
Czy coś jest gdzieś wysyłane?
Nie. Wszystko jest obliczane w Twojej przeglądarce, a ostatnie ustawienia zostają w pamięci lokalnej tej przeglądarki.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora