Najdluzszy Podciag Rosnacy

Romualda Laskowska

Longest Increasing Sequence – LIS – Najdłuższy podciąg rosnący

Najdłuższy oznacza, że nie ma dłuższych. Podciąg: ciąg powstały poprzez wybranie pewnej liczby elementów ciągu początkowego.
Załóżmy, że dany jest ciąg liczb an. Jeśli z ciągu an wybierzemy w dowolny sposób pewną ilość wyrazów, które ponownie ustawimy w ciąg zachowując ich kolejność w ciągu an, to otrzymany w ten sposób ciąg nazywamy podciągiem ciągu an.
Podciągami ciągu: 3 6 7 2 1 8 9 5 są np.
3 6
3 7 1 5
6 2 9
9
3 6 7 2 1 8 9 5
Jeśli każda para sąsiednich wyrazów podciągu spełnia warunek: bi<bi+1, to podciąg bn nazywamy rosnącym.
Ciąg powyższy ma dosyć sporo podciągów rosnących (3-6, 3-7-8, 2) - najdłuższym z nich jest podciąg 3-6-7-8-9. Wyznaczanie najdłuższego rosnącego podciągu poprzez analizę wszystkich możliwych podciągów nie jest algorytmem efektywnym za względu na złożoność wykładniczą: O(2n). Podciąg taki można wyznaczyć metodą programowania dynamicznego, która wymaga tylko niewielkiej ilość pamięci, ale za to zwróci wynik w czasie O(n2).
Weźmy ciąg pięcioelementowy a1, a2, a3, a4, a5. Gdyby najdłuższy rosnący podciąg miałby się rozpoczynać wyrazem ostatnim a5, to jego maksymalna długość wynosiłaby 1. Gdyby najdłuższy rosnący podciąg rozpoczynał się wyrazem a4, to mógłby mieć maksymalną długość 2 o ile a4<a5 - jeśli tak nie jest, to maksymalna długość podciągu rosnącego jaki możemy uzyskać rozpoczynając go w tym miejscu wynosi 1.
Jeśli to samo rozumowanie przeniesiemy do wyrazu a3, to tylko nieznacznie ulegnie ono skomplikowaniu. Gdyby a3 miałoby być początkiem najdłuższego rosnącego podciągu, to wówczas najdłuższy rosnący podciąg będzie o jeden dłuższy od najdłuższego rosnącego podciągu zaczynającego się od a4 lub a5 pod warunkiem, że są one większe od a3. Oznaczając przez DL[i] długość najdłuższego podciągu rosnącego jaki można uzyskać rozpoczynając go wyrazem i, wartość DL[1]otrzymamy za pomocą pętli

DL[5]:=1;
//Sposrod wszystkich kandydatow na nastepny wyraz podciagu //rosnącego wybierz tego, ktory da najdluzszy mozliwy podciag                 
for (int i=4; i>=1; i--)
    for(int j=i+1;i<=5;i++)
        if(a[j]>a[i])
            if(DL[j]+1>DL[i])
              DL[i]:=DL[j]+1;

To samo rozumowanie można zastosować dla dowolnego wyrazu ciągu i:

DL[n]:=1;
for(int i=n-1; i>=1; i--)
   for(int j=i+1; j<=n; j++)
  if((a[j]>a[i]) && (DL[j]+1)>DL[i]))
      DL[i]:=DL[j]+1;

Po zakończeniu pętli największa liczba w tablicy jest długością najdłuższego podciągu.
Ten algorytm działa w czasie O(n2) (bo dla każdego elementu przejrzymy wszystkie poprzednie, czyli łącznie wykonamy 1+2+…+n-1 porównań, co daje czas kwadratowy).
Możemy też wykorzystać następujący algorytm dynamiczny - dla ustalonego wyniku (długości podciągu) pamiętamy najmniejszy element, którym może się kończyć podciąg rosnący o zadanej długości.:

1. A ← pusta lista wektorów (lista warstw)
2. Dla każdego elementu z ciągu:
Znajdź w A umiejscowienie danego elementu w najdłuższym rosnącym podciągu: wyszukaj binarnie pierwszą taką warstwę, że jej ostatni element jest większy od danego Jeżeli takiego wektora nie ma to dodaj nową warstwę na końcu A.
3. LIS to ciąg pierwszych elementów z każdego wektora       w wektorze A

Czas: Θ(n lg n)

Algorytm:

vector<int> Warstwa[n];
int Ostatni = 0, index;
for (int i=0; i<n; i += 1)
    wczytaj(A);
    index = lower_bound(Warstwa.back, A);
    //Czyli najmniejszy element większy od A (lub równy!).

    Warstwa[index].Push_Back(A);
    Ostatni = max(Ostatni, index); 
 //tutaj bierzemy maksimum ze wszystkich numerów
 //niepustych warstw
wypisz(Ostatni);

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.

obrazek_LIS.jpg

Jeśli 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). 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.
Najprościej nie modyfikować w ogóle struktury, tylko,, idąc "od tyłu", zachłannie wybierać pasujące nam elementy. Ale uwaga! 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 ż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. 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.

Zadanie:

Najdłuższy Wspólny Rosnący – zadanie z ILOCAMP 2010 można znaleźć tu

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License