Dana jest tablica zawierająca $n$ liczb: $a$.Zadanie polega na znalezieniu najdłuższego, ściśle rosnącego, podciągu w $a$.

Formalnie szukamy najdłuższego ciągu o indeksach $i_1, i_k$ takich, że $$i_1 < i_2 < i_k,a < i_k,a < i_k,a$$

W tym artykule omówimy wiele algorytmów do rozwiązania tego zadania.Ponadto omówimy kilka innych problemów, które można sprowadzić do tego problemu.

Rozwiązanie w $O(n^2)$ za pomocą programowania dynamicznego

Programowanie dynamiczne jest bardzo ogólną techniką, która pozwala na rozwiązywanie ogromnej klasy problemów.Tutaj zastosujemy tę technikę do naszego konkretnego zadania.

Na początku będziemy szukać tylko długości najdłuższego rosnącego podciągu, a dopiero później dowiemy się, jak odtworzyć sam podciąg.

Znajdowanie długości

Aby wykonać to zadanie, definiujemy tablicę $d$, gdzie $d$ jest długością najdłuższego rosnącego podciągu, który kończy się elementem o indeksie $i$.Tę tablicę będziemy obliczać stopniowo: najpierw $d$, potem $d$, i tak dalej.Po obliczeniu tej tablicy odpowiedzią na problem będzie maksymalna wartość w tablicy $d$.

Pozwólmy więc, aby bieżącym indeksem był $i$.Tzn. chcemy obliczyć wartość $d$, a wszystkie poprzednie wartości $d, d$ są już znane.Wtedy są dwie możliwości:

• $d = 1$: wymagany podciąg składa się tylko z elementu $a$.
• $d > 1$: wtedy w wymaganym podciągu jest jeszcze jedna liczba przed liczbą $a$. Skupmy się na tej liczbie: może to być dowolny element $a$ z $j = 0 i-1$ i $a < a$.W ten sposób możemy obliczyć $d$ za pomocą następującego wzoru:Jeśli ustalimy indeks $j$, to najdłuższy rosnący podciąg kończący się na dwóch elementach $a$ i $a$ ma długość $d + 1$.Wszystkie te wartości $d$ są już znane, więc możemy bezpośrednio obliczyć $d$ za pomocą:$d = \max_{substack{j = 0 \dots i-1 \ a < a}} \left(d + 1\right)$$

Jeśli połączymy te dwa przypadki, otrzymamy ostateczną odpowiedź dla $d$:

$d = \max_{substack{j = 0 \dots i-1 \ a < a} \$$

Implementacja

Tutaj znajduje się implementacja opisanego powyżej algorytmu, który oblicza długość najdłuższego rosnącego podciągu.

int lis(vector<int> const& a) { int n = a.size(); vector<int> d(n, 1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a < a) d = max(d, d + 1); } } int ans = d; for (int i = 1; i < n; i++) { ans = max(ans, d); } return ans;}

Przywracanie podciągu

Do tej pory dowiedzieliśmy się tylko jak znaleźć długość podciągu, ale nie jak znaleźć sam podciąg.

Aby móc odtworzyć podciąg generujemy dodatkową pomocniczą tablicę $p$, którą będziemy obliczać obok tablicy $d$.$p$ będzie indeksem $j$ drugiego ostatniego elementu w najdłuższym rosnącym podciągu kończącym się na $i$.Innymi słowy indeks $p$ jest tym samym indeksem $j$, przy którym uzyskano najwyższą wartość $d$.Ta pomocnicza tablica $p$ wskazuje w pewnym sensie na przodków.

Potem, aby wyprowadzić podciąg, po prostu zaczynamy od indeksu $i$ z maksymalną wartością $d$ i podążamy za przodkami, aż wydedukujemy cały podciąg, czyli aż dojdziemy do elementu o wartości $d = 1$.

Implementacja przywracania

Zmienimy nieco kod z poprzednich rozdziałów.Obliczymy tablicę $p$ obok $d$, a po niej obliczymy następstwo.

Dla wygody oryginalnie przypiszemy przodkom wartość $p = -1$.Dla elementów z $d = 1$ wartość przodków pozostanie $-1$, co będzie nieco wygodniejsze przy przywracaniu następstwa.

vector<int> lis(vector<int> const& a) { int n = a.size(); vector<int> d(n, 1), p(n, -1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a < a && d < d + 1) { d = d + 1; p = j; } } } int ans = d, pos = 0; for (int i = 1; i < n; i++) { if (d > ans) { ans = d; pos = i; } } vector<int> subseq; while (pos != -1) { subseq.push_back(a); pos = p; } reverse(subseq.begin(), subseq.end()); return subseq;}

Alternatywny sposób przywracania podciągu

Możliwe jest również przywrócenie podciągu bez tablicy pomocniczej $p$.Możemy po prostu przeliczyć aktualną wartość $d$, a także sprawdzić, w jaki sposób osiągnięto maksimum.

Ta metoda prowadzi do nieco dłuższego kodu, ale w zamian oszczędzamy trochę pamięci.

Rozwiązanie w $O(n ^2)$ za pomocą programowania dynamicznego i wyszukiwania binarnego

Aby uzyskać szybsze rozwiązanie problemu, konstruujemy inne rozwiązanie programowania dynamicznego, które działa w $O(n^2)$, a później poprawiamy je do $O(n ^2)$.

Użyjemy tablicy programowania dynamicznego $d$.Tym razem $d$ będzie elementem, na którym kończy się podciąg o długości $i$.Jeśli jest wiele takich ciągów, to bierzemy ten, który kończy się na najmniejszym elemencie.

Początkowo zakładamy $d = -infty$, a dla wszystkich pozostałych elementów $d = \infty$.

Ponownie będziemy stopniowo przetwarzać liczby, najpierw $a$, potem $a$, itd. i w każdym kroku utrzymywać tablicę $d$ tak, aby była aktualna.

Po przetworzeniu wszystkich elementów $a$ długość pożądanego podciągu jest największa $l$ z $d < \infty$.

int lis(vector<int> const& a) { int n = a.size(); const int INF = 1e9; vector<int> d(n+1, INF); d = -INF; for (int i = 0; i < n; i++) { for (int j = 1; j <= n; j++) { if (d < a && a < d) d = a; } } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

Poczynimy teraz dwie ważne obserwacje.

Tablica $d$ będzie zawsze posortowana: $d$ dla wszystkich $i = 1 ∗ n$.A także element $a$ będzie aktualizował co najwyżej jedną wartość $d$.

Dlatego możemy znaleźć ten element w tablicy $d$ za pomocą wyszukiwania binarnego w czasie $O(∗ n)$.W rzeczywistości po prostu szukamy w tablicy $d$ pierwszej liczby, która jest ściśle większa od $a$, i próbujemy zaktualizować ten element w taki sam sposób jak w powyższej implementacji.

Implementacja

int lis(vector<int> const& a) { int n = a.size(); const int INF = 1e9; vector<int> d(n+1, INF); d = -INF; for (int i = 0; i < n; i++) { int j = upper_bound(d.begin(), d.end(), a) - d.begin(); if (d < a && a < d) d = a; } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

Przywracanie podciągu

Za pomocą tego podejścia możliwe jest również przywracanie podciągu.Tym razem musimy utrzymywać dwie tablice pomocnicze.Jedna, która mówi nam o indeksie elementów w $d$.I znowu musimy stworzyć tablicę „przodków” $p$.$p$ będzie indeksem poprzedniego elementu dla optymalnego podciągu kończącego się na elemencie $i$.

Łatwo jest utrzymywać te dwie tablice w trakcie iteracji nad tablicą $a$ obok obliczeń $d$.A na końcu nie jest trudno odtworzyć pożądany podciąg za pomocą tych tablic.

Rozwiązanie w $O(n \log n)$ za pomocą struktur danych

Zamiast powyższej metody obliczania najdłuższego rosnącego podciągu w $O(n \log n)$ możemy też rozwiązać problem w inny sposób: za pomocą kilku prostych struktur danych.

Powróćmy do pierwszej metody.Pamiętajmy, że $d$ jest wartością $d + 1$ przy $j < i$ i $a < a$.

Tak więc jeśli zdefiniujemy dodatkową tablicę $t$ taką, że $$t] = d,$$ to problem obliczenia wartości $d$ jest równoważny znalezieniu maksymalnej wartości w prefiksie tablicy $t$:$$d = $maksymalna wartość w prefiksie tablicy $t$

Problem znalezienia maksimum w prefiksie tablicy (który się zmienia) jest standardowym problemem, który może być rozwiązany przez wiele różnych struktur danych. Na przykład możemy użyć drzewa Segmenta lub drzewa Fenwicka.

Metoda ta ma oczywiście pewne wady: pod względem długości i złożoności implementacji będzie gorsza od metody wykorzystującej wyszukiwanie binarne.Dodatkowo, jeśli liczby wejściowe $a$ są szczególnie duże, to będziemy musieli zastosować pewne sztuczki, takie jak kompresja liczb (np. przenumerować je z $0$ do $n-1$), lub użyć niejawnego drzewa Segmenta (generować tylko te gałęzie drzewa, które są ważne).W przeciwnym razie zużycie pamięci będzie zbyt duże.

Z drugiej strony ta metoda ma również pewne zalety: dzięki niej nie trzeba myśleć o żadnych skomplikowanych własnościach w rozwiązaniu programowania dynamicznego.I to podejście pozwala nam bardzo łatwo uogólnić problem (patrz poniżej).

Zadania pokrewne

Istnieje kilka problemów, które są ściśle związane z problemem znajdowania najdłuższego rosnącego podciągu.

Najdłuższy nie malejący podciąg

To jest w rzeczywistości prawie ten sam problem. Tylko teraz dozwolone jest użycie identycznych liczb w podciągu.

Rozwiązanie jest w zasadzie również prawie takie samo.Musimy tylko zmienić znaki nierówności i nieco zmodyfikować wyszukiwanie binarne.

Liczba najdłuższych rosnących podciągów

Możemy skorzystać z pierwszej omawianej metody, albo z wersji $O(n^2)$, albo z wersji wykorzystującej struktury danych.Musimy tylko dodatkowo zapisać na ile sposobów możemy otrzymać najdłuższe rosnące podciągi kończące się wartościami $d$.

Liczba sposobów na utworzenie najdłuższego rosnącego podciągu kończącego się na $a$ jest sumą wszystkich sposobów dla wszystkich najdłuższych rosnących podciągów kończących się na $j$, gdzie $d$ jest maksymalne.Takich $j$ może być wiele, więc musimy je wszystkie zsumować.

Używając drzewa segmentowego to podejście można również zaimplementować w $O(n log n)$.

Nie jest możliwe użycie do tego zadania podejścia wyszukiwania binarnego.

Najmniejsza liczba nierosnących podciągów pokrywających ciąg

Dla danej tablicy z $n$ liczbami $a$ musimy pokolorować liczby w najmniejszej liczbie kolorów, tak aby każdy kolor tworzył nierosnący podciąg.

Aby to rozwiązać, zauważamy, że minimalna liczba wymaganych kolorów jest równa długości najdłuższego rosnącego podciągu.

Dowód:Musimy udowodnić dwoistość tych dwóch problemów.

Oznaczmy przez $x$ długość najdłuższego rosnącego podciągu, a przez $y$ najmniejszą liczbę nierosnących podciągów, które tworzą pokrycie.Musimy udowodnić, że $x = y$.

Jasno widać, że $y < x$ nie jest możliwe, bo jeśli mamy $x$ ściśle rosnących elementów, to żadne dwa nie mogą być częścią tego samego nierosnącego podciągu.Mamy zatem $y < x$.

Wykażemy teraz, że $y > x$ nie jest możliwe przez sprzeczność.Załóżmy, że $y > x$.Wtedy rozważamy dowolny optymalny zbiór $y$ nierosnących podciągów.Przekształcamy ten zbiór w następujący sposób: o ile istnieją dwa takie podciągi takie, że pierwszy zaczyna się przed drugim podciągiem, a pierwszy ciąg zaczyna się od liczby większej lub równej drugiemu, to odhaczamy tę liczbę początkową i dołączamy ją do początku drugiego.Po skończonej liczbie kroków mamy $y$ podciągów, a ich numery początkowe będą tworzyć rosnący podciąg o długości $y$.Ponieważ założyliśmy, że $y > x$ doszliśmy do sprzeczności.

Z tego wynika, że $y = x$.

Przywracanie sekwencji:Pożądany podział sekwencji na podciągi może być wykonany zachłannie.Tzn. przechodzimy od lewej do prawej i przypisujemy bieżący numer lub ten podciąg kończący się minimalnym numerem, który jest większy lub równy bieżącemu.

Problemy z praktyki

• Topcoder – IntegerSequence
• Topcoder – AutoMarket
• Kodery – Tourist
• Kodery -. LCIS
• SPOJ – SUPPER
• Topcoder – BridgeArrangement
• ACMSGURU – „North-East”

.