Najdłuższy Podciąg Rosnący

Najdłuższy Podciąg Rosnący

szerzej znany jako

Longest Increasing Subsequence

.
Problem polega na tym, aby mając zadany ciąg A [ ] długości n, odnaleźć najdłuższy występujący w nim podciąg silnie rosnący.
Generalnie do naszych potrzeb (czytaj zadania L) wystarczy nam odnalezienie jego długości.

Sposób 1.

Jasny, prosty i przyjemny, ale wolniejszy (kwadratowy).

Mamy ciąg A. Sortujemy go i tak powstaje …. nie, nie Chocapic. Tak powstaje ciąg B. Teraz tylko wystarczy znaleźć ich najdłuższy wspólny podciąg (co już oczywiście umiemy zrobić).
Zlożoność: O ( n*n + n*log n)=O(n*n)

Sposób 2.

Bardziej magiczny, również przyjemny, bo szybszy O (n log n). Słowem Właściwy_i_Obowiązujący.

Mamy tablicę liczb całkowitych T [ ]
T [ s ] -najmniejsza liczba, na której kończy się podciąg długości s. Czyli jeśli mamy do wyboru następujące ciągi 1 3 4 oraz 2 4 5, to T [ 3 ]= 4.
Jeśli nie ma takiego ciągu, T [ s ]= infinity (dla nie-angielskich: nieskończoność).

pseudo-kod

T[0]=0;
for ( i=1;i<=n; i++ )
T [ i ] = inf; //inf tj. Bardzo Duża Liczba, czytaj suma wyrazów ciągu+1

for (k=0;k<n;k++)
{
znajdz_s_takie_ze T [s ] <A [k ] && T [ s+1] > A[ k ];
T[ s+1]=A [k];
}

teraz rozwińmy praktycznie pseufofunckję znajdz_takie_s_ze

Kochany wujek STL posiada następującą miłą własność: lower_bound ( p, q, u )
gdzie p-początek przeszukiwanego zakresu
q- koniec przeszukiwanego zakresu
u- czego szukamy
dla nas to lower_band (T, T+n+1, A [k] )
Powyższa funkcja zwraca wskaźnik na pierwszy element większy od zadanej wartości.

Na koniec dobrze by było znaleźć szukaną długość największego rosnącego podciągu. Otóż jest to największy indeks komórki tablicy T [] takiej, że owa komórka nie zawiera nieskończoności.

Jak to działa

Dla lepszego zrozumienia proponuję metodę DIY-zrób to sam, a następnie sprawdzenie z tym, co poniżej.

Przykład na ciągu 1 4 2 4 5 3 6 w tablicy A [ ]

k=0;
A [ 0 ]=1;
T [ 0 ]=0; T [ 1 ]=inf;
czyli
s=0; oraz T [ 1 ]=1;

k=1
A [ 1 ]=4 T [ 1 ]=1 T [ 2 ]=inf;
=> s=1 T [2 ]=4

k=2
A [ 2 ]=2 T [ 1 ]=1 T [ 2 ]=1
=> s=1 T [ 2 ]=2

k=3
A [ 3 ]= 4 T [ 2 ]=2 T [ 3 ]=inf
=> s=2 T [ 3 ]= 4

k=4
A [ 4 ]=5 T [3 ]= 4 T [ 4 ]=inf
=> s=3 T [ 4 ]= 5

k=5
A [ 5 ]=3 T [ 2 ]=2 T [ 3 ]=4
=> s=2 T [ 3 ]=3

k=6
A [ 6 ]=6 T [ 4 ]=5 T [ 5 ]=inf
=> s=4 T [ 5 ]=6

W efekcie otrzymujemy tablicę T [ 0 1 2 3 5 6 ]. Ponieważ ostanią komórką o wartości mniejszej od inf jest T [5], to długość LIS wynosi 5.
Zważając na to, że T [ ] jest ściśle rosnąca (ad.1), nie będzie podciągu o większej długości (ad.2).
ad.1
Nie może być inaczej, gdyż zawsze wpisujemy najmniejszą możliwą liczbę w danym miejscu, więc niemożliwe jest, aby wpisać coś mniejszego później ( a to by powodowało nieposortowanie T [ ] ).
ad. 2
Gdyby był jakiś ciąg o większej długości, to wtedy istniałaby jakaś liczba h, której w naszej tablicy nie ma, na której ów się kończy. Ale wpisaliśmy wszystkie możliwe liczby w naszych dostępnych długościach ciągów.

W razie nieścisłości, błędów, niejasności proszę pisać.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License