Zadanie – Longest Increasing Sequence

W podanym ciągu liczb znajdź najdłuższy podciąg rosnący.
Przykład:
Wejście: 5 1 4 2 3 1 2 9 1
Wynik: 1 2 3 9

Rozwiązanie – programowanie dynamiczne

Zamiast podejścia naiwnego, chcemy zastosować programowanie dynamiczne.

Główna idea kryjąca się za określeniem programowania dynamicznego to rozwiązanie skomplikowanego problemu poprzez rozbicie go na kilka mniejszych problemów i dokonania obliczeń na nich. W późniejszym etapie rezultaty składowe są wykorzystywane do uzyskania wyniku problemu głównego. Jak moglibyśmy rozbić ten problem na mniejsze problemy? Czy jeśli mamy ciąg A, gdzie znamy wartość dla każdego jego elementu oraz wiemy, ile wynosi najdłuższy podciąg kończący się na danym elemencie L, to możemy tę wiedzę jakoś wykorzystać do obliczenia najdłuższego podciągu po dodaniu dodatkowego znaku do A?

Rozważmy następującą sytuację:

Programowanie dynamiczne

Mamy ciąg A = {5,1,4,2 } oraz wiemy, ile wynosi najdłuższy możliwy podciąg kończący się na danej pozycji L = {1, 1, 2, 2 }. Jak możemy wykorzystać tę wiedzę do obliczenia, ile będzie wynosił najdłuższy możliwy podciąg po dodaniu do naszego ciągu liczby 3? Rozważmy wszystkie możliwości:

  • {5,3} najdłuższy możliwy podciąg ma długość 1. Ponieważ liczba 3 jest mniejsza niż ostatni element naszego ciągu o dotychczasowej długości 1, więc nie może być wykorzystana do jego przedłużenia.
  • {1, 3} mieliśmy ciąg o długości 1 kończący się liczbą 1. Jeśli dodamy do niego na koniec liczbę 3, to ponieważ 3>1, możemy wydłużyć nasz podciąg o 1.
  • {X,4,3} – mamy dwuelementowy ciąg, gdzie ostatni jego element to 4, a ponieważ 3 jest mniejsze niż 4, nie możemy przedłużyć tego ciągu.
  • {X,2,3} – ostatni element ciągu o długości 2 jest mniejszy od nowego elementu, więc razem z nowym elementem możemy utworzyć podciąg o długości trzy.

Po dodaniu na koniec liczby 3 możemy przedłużyć dwa istniejące podciągi (zgodnie z warunkiem, aby nowa wartość była większa niż ostatnia w istniejącym podciągu). Najdłuższy możliwy podciąg, jaki możemy uzyskać, ma długość 3.

Analogicznie możemy postąpić w poniższej sytuacji:

Programowanie dynamiczne

Widzimy, że mamy ciąg o długości 3, zakończony wartością 3, ostatnia wartość jest mniejsza niż nowa wartość 9. Możemy przedłużyć ten ciąg i uzyskamy {X, X, 3, 9}. Wzór na nową maksymalną długość podciągu rosnącego wynosi: L(i) =MAX(L(j) | j < i, A[j] < A[i]) + 1. Jeśli chcemy łatwo odtworzyć cały ciąg, a nie tylko znać jego długość, to musimy dla każdego podciągu przechowywać również index elementu poprzedniego:

Programowanie dynamiczne

Kod Python oraz c++

def LongestIncreasingSequence( dane ):
    L = [ 0 for a in dane]
    Ref = [ -1 for a in dane]
    maxCount=0
    currentMaxIndex = -1


    for i, val_i in enumerate(dane):
        for j in range(0,i):
            val_j = dane[j]
            if val_i <= val_j:
                continue;
            if L[j]+1 > L[i]:
                L[i] = L[j]+1
                Ref[i] = j
        if L[i] > maxCount:
            maxCount = L[i]
            currentMaxIndex = i


    vec = [];
    while currentMaxIndex != -1:
        vec.insert(0,dane[currentMaxIndex])
        currentMaxIndex = Ref[currentMaxIndex]
    return vec

#include <iostream>
#include <algorithm>

using namespace std;

vector<int> LongestIncreasingSequence( vector<int>& dane )
{
    int ilosc = dane.size();
    vector<int> L(ilosc,0);
    vector<int> Ref(ilosc,-1);

    int maxCount=0, currentMaxIndex = -1;

    for ( int i = 0; i < ilosc; ++i )
    {
        for ( int j = 0; j < i; ++j )
        {
            if ( dane[i] <= dane[j] ) continue;
            if ( L[j]+1 > L[i] )
            {
                L[i] = L[j]+1;
                Ref[i] = j;
            }
        }
        if ( L[i] > maxCount ) {
            maxCount = L[i];
            currentMaxIndex = i;
        }
    }

    vector<int> vec;
    while (currentMaxIndex != -1) {
        vec.push_back(dane[currentMaxIndex]);
        currentMaxIndex = Ref[currentMaxIndex];
    }
    std::reverse(vec.begin(),vec.end());

    return vec;
}

Dyskusja złożoności

Musimy dokonać alokacji pamięci dla naszej tablicy najdłuższych podciągów. Robimy to dla dwóch elementów, wiec mamy liniową złożoność pamięciową. Zaczynamy od ciągu długości zero i kolejno dodajemy nowe elementy. Elementów jest N i dla każdego musimy dokonać sprawdzenia z każdym istniejącym elementem, więc mamy kwadratową złożoność obliczeniową O(N^2).

Wytłumaczenie Video [EN]

Odnośniki