Najdłuższy podciąg rosnący

25.11.2009 - Karol Konaszyński
TrudnośćTrudność

Właściwy algorytm

Tworzymy sobie listę warstw (czyli np. wektor wektorów liczb) i będziemy ją uzupełniać podobnie jak w naszym dynamiku.
Niech $ A $ będzie (coraz to kolejnym) elementem ciągu. Szukamy, binary searchem, największego takiego $ k $, żeby $ A $ mógł przedłużyć podciąg o długości $ k $. Czyli warstwy o jak największym numerze $ k $ takiej, żeby istniał w niej element mniejszy od $ A $. Jeśli dodatkowo postaramy się, żeby elementy w warstwach były posortowane malejąco, to wystarczy patrzeć tylko na "ogony" tych warstw/wektorów (ostatnie elementy). Zatem problem sprowadza się do znalezienia największej liczby mniejszej od zadanego $ A $, co już potrafimy (powinniśmy potrafić?) zrobić...

Co dalej? Skoro znaleźliśmy takie $ k $, to znaczy, że $ A $ przedłuża podciąg rosnący o długości $ k $ i żadnego dłuższego. Czyli musimy wrzucić element $ A $ do warstwy/listy następnej, $ k+1 $-szej. Oczywiście, będzie on tam najmniejszy (gdyby istniał mniejszy, to $ A $ znalazłby się w którejś z następnych warstw) czyli wędruje po prostu na koniec tej listy/wektora.
Koniec algorytmu! Aha, tylko co należy wypisać? Otóż LAS tego ciągu będzie długości takiej jak numer najdalszej, niepustej warstwy (bo tam będą siedziały elementy kończące najdłuższe podciągi rosnące). A ponieważ warstwy uzupełniają nam się po kolei, czyli nie będzie "dziur", zwracamy po prostu ich ilość.

Ważne w tym algorytmie jest to, że jest online! Czasem może nam się to przydać... Natomiast jego złożoność szacujemy przez $ n $ razy czas wykonania binary-searcha, czyli $ O\left(n*log(n)\right) $.
Oto algorytm w pseudokodzie:

vector<int> Layers[n];
int LongestEver = 0, Index;
for (int i=0; i<n; i += 1)
    scanf(A);
    Index = lower_bound(Layers.back, A);
    /*Czyli najmniejszy element większy od A (lub równy!).
Zadanie bojowe dla czytelników: jak zaimplementować powyższą linijkę?
    można użyć stl-owego lower_bound, ale to trochę zabawy;
    proponuję napisanie własnej funkcji.*/
    Layers[Index].Push_Back(A);
    LongestEver = max(LongestEver, Index);
    /*tutaj bierzemy maksimum ze wszystkich numerów niepustych warstw*/
printf(LongestEver);

Przykład. Oto jak będzie wyglądała nasza struktura jeden krok przed zakończeniem działania algorytmu dla ciągu: $ 3\ 4\ 2\ 3\ 7\ 6\ 5\ 6\ 8\ 5\ 9\ 4 $.

Skoro już umiemy liczyć długość takiego podciągu, zastanówmy się nad modyfikacją tego algorytmu umożliwiającą nam wypisanie go. Otóż przy każdym elemencie możemy pamiętać lokalizację poprzedniego (a nie tylko jego wartość, bo niektóre mogą być równe i sama wartość nic nam nie powie!). Czyli zamiast wrzucać do list elementy, wrzucamy pary: [wartość, indeks na liście poprzedniego elementu]. Wtedy idąc "od końca" (od dowolnego elementu z ostatniej warstwy), możemy odtworzyć cały ciąg.

Jeśli jednak zależy nam na pamięci albo pewnych własnościach tych LAS-ów (jako że może być ich kilka, a zostaniemy zapytani o jakiś specyficzny), musimy to zrobić inaczej. Najprościej nie modyfikować w ogóle struktury, tylko,, idąc "od tyłu", zachłannie wybierać pasujące nam elementy. Ale uwaga, pułapka! Otóż nie możemy jako poprzednika wziąć dowolnego elementu z warstwy poprzedniej, bo mógł zostać dodany później.
Rozważmy przykład:
$ 2\ 3\ 1 $
Wtedy w kolejnych warstwach będą:
warstwa 1: $ 2, 1 $
warstwa 2: $ 3 $.
Po wybraniu elementu $ 3 $ kusi, żeby wziąć $ 1 $. Ale $ 1,3 $ nie tworzą podciągu!

Najprostszą metodą jest, mając ustalony element $ A $ w warstwie $ k+1 $, wybrać z warstwy o numerze $ k $ największy mniejszy od tego elementu. Czemu to jest dobrze? Bo wiemy (a przynajmniej jesteśmy przekonani) że nasz algorytm jest poprawny, czyli istnieje taki element w warstwie $ k $-tej, że można go przedłużyć elementem $ A $. Ale skoro elementy są posortowane nierosnąco po wartości i rosnąco po indeksie, to $ A $ również przedłuży podciąg kończący się większym elementem, bo ten ma jednocześnie mniejszy indeks.

Zobaczmy, jak to wygląda na naszym rysunku: element '7' został dodany do trzeciej warstwy "z powodu" elementu '3' (czyli '3' była w drugiej warstwie, kiedy do trzeciej dopisaliśmy '7'). Ale '7' tym bardziej przedłuża podciąg kończący się na '4', bo '4' (będąc wcześniej w warstwie) ma mniejszy indeks.

Trochę matematyki

Rozważmy takie zadanie: Dany jest ciąg liczb o długości większej od $ M^{2} $. Pokazać, że istnieje w nim podciąg monotoniczny o długości większej od $ M $. Dowód korzystający z algorytmu: po odpaleniu go dla tego ciągu podzielimy jego elementy na warstwy. Gdyby było ich więcej niż $ M $, to istniałby podciąg rosnący o takiej długości. Jeśli nie, to w którejś warstwie musiałoby być ponad $ M $ elementów. Ale wiemy, że w obrębie jednej warstwy elementy tworzą ciąg nierosnący, czyli też monotoniczny - koniec dowodu.
Taką samą argumentację można użyć do dowodu faktu: W każdym nieskończonym ciągu jest nieskończony podciąg monotoniczny (dla bardzo wtajemniczonych: dowodzi to błyskawicznie twierdzenia Bolzano-Weierstrassa. Fajnie, nie?...)
Zastanówmy się teraz nad pewnymi wariacjami problemu szukania LAS-u.

3.666665
Twoja ocena: Brak Ocena: 3.7 (15 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com