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ć.
