Dynamik - najdłuższy podciąg rosnący

Zastanówmy się nad następującym problemem. Na półce stoi dwanaście tomów encyklopedii. Ich kolejność, wskutek wielokrotnego użytkowania, jest dosyć przypadkowa:

11, 1, 10, 4, 3, 2, 8, 7, 12, 6, 9, 5.

W jednym ruchu możesz wyjąć dowolny tom i umieścić go w dowolnym miejscu, (przyjmujemy że pozostałe tomy w razie takiej konieczności bezboleśnie się przesuną). W jakiej najmniejszej liczbie ruchów możesz uporządkować wszystkie tomy, tak aby były ustawione w naturalnej kolejności od 1 do 12?

Rozwiązanie tego problemu może się nasunąć kiedy zastanowimy się które tomy mogłyby pozostać nietknięte na półce (nie będziemy ich wyciągać), jak może wyglądać zbiór tomów, które mogą nie zostać ani razu przestawione tak byśmy mogli zminimalizować ilość tych, które musimy zdjąć z półki i przestawić? Zbiór tomów, które mogą nie zostać ani razu ruszone, musi, oczywiście, stanowić najdłuższy podciąg rosnących numerów tomów. Oczywiście nie chodzi tu o spójny fragment ciągu numerów tomów.

11, 1, 10, 4, 3, 2, 8, 7, 12, 6, 9, 5.

Tomy zaznaczone na czerwono mogłyby pozostać w swoim miejscu, wtedy do przestawienia pozostałoby 9 tomów (12-3=9). Czy znajdziesz dłuższy podciąg rosnący?

W tym wypadku długość najdłuższego rosnącego podciągu wynosi 4.

Jak w systematyczny sposób wyznaczyć długość najdłuższego podciągu rosnącego naszego ciągu?

Można dla każdego elementu policzyć długość najdłuższego podciągu rosnącego kończącego się na nim, a potem wziąć największą spośród tych wartości. Dla każdego z pierwszych dwóch tomów szukanym wynikiem jest 1. Trzeci tom ma numer 10, więc można za jego pomocą przedłużyć jednoelementowy ciąg rosnący kończący się na tomie numer 1, otrzymując ciąg długości 2. Podobnie ma się sytuacja w przypadku każdego z kolejnych trzech tomów: 4, 3, 2. Za pomocą tomu numer 8 można przedłużyć dowolny z czterech dwuelementowych ciągów, które znaleźliśmy wcześniej. Podobnie można postąpić z tomem numer 7.

Widać już, jak kontynuować te obliczenia – wystarczy każdorazowo wybierać najdłuższy ciąg spośród dotychczas utworzonych, kończący się tomem o numerze mniejszym niż numer rozważanego tomu, i ten właśnie ciąg przedłużać. W ten sposób otrzymamy następującą tabelkę wyników:

Stąd najmniejsza konieczna liczba ruchów jest równa 12 - 4 = 8.

Tak właśnie działają tzw. dynamiki. Rozwiązanie dynamiczne to takie, w którym do policzenia pewnej wartości używamy wartości policzonych już wcześniej.

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 jednak doprowadzić ten algorytm w prosty sposób do złożoności O(nlogn). Wystarczy, że przeorganizujemy tablicę. Będziemy dla każdej długości podciągu pamiętać najmniejszy element, którym może się kończyć podciąg rosnący o zadanej długości.

Mamy teraz więc tablicę, której indeksami są kolejne długości podciągów.

Oto nasz ciąg: 11, 1, 10, 4, 3, 2, 8, 7, 12, 6, 9, 5.

Dla każdego kolejnego bieżącego numeru tomu z ciągu:

1. szukamy największego spośród mniejszych od niego (bo próbujemy za pomocą naszego bieżącego numeru przedłużyć jeden z wcześniej odnalezionych podciągów),

2. Przechodzimy do indeksu jeden większego niż odnaleziony w pkt.1 i jeśli wartość tam zapisana jest większa od naszego bieżącego numeru tomu, to ją zmieniamy na naszą wartość.

Dla ułatwienia pisania kodu wpisujemy wartość 0 pod zerowym indeksem, a bardzo dużą wartość w pozostałych komórkach.

Bierzemy pod uwagę pierwszą liczbę z ciągu wejściowego, liczbę 11, szukamy w tablicy wynikowej największej wartości spośród mniejszych od 11, jest to 0 zapisane pod indeksem zerowym, a więc przechodzimy do kolejnego indeksu, którym jest indeks 1 (tak jakbyśmy przedłużali podciąg rosnący o długości zero do długości jeden) i wpisujemy tam naszą 11, gdyż jest ona mniejsza od nieskończoności. Bierzemy kolejną wartość z ciągu wejściowego, jest nią jedynka, szukamy największej wartości, która jest mniejsza od 1, znajdujemy ponownie zero, ponownie więc próbujemy przedłużyć podciąg o długości zero do długości jeden, podejmujemy decyzję że jedynka jest mniejsza od zapisanej tam jedenastki, a więc zapamiętujemy jedynkę pod indeksem 1. Kolejny element z ciągu to 10, szukamy największej wartości takiej by była mniejsza niż 10, znajdujemy jedynkę pod indeksem 1, co oznacza, że za pomocą naszej 10 przedłużymy do dwóch podciąg rosnący o długości 1

Postępujemy podobnie do końca elementów z ciągu wejściowego. Uzyskujemy następujący wynik:

Długością najdłuższego podciągu rosnącego (LAS) jest liczba 4 (ostatni indeks, który uzyskał swoją wartość). Złożoność zaprezentowanego podejścia nadal jest O(n²), gdyż dla każdego elementu w ciągu wejściowym przeszukujemy całą tablicę wynikową w poszukiwaniu największego elementu mniejszego od niego. Jednak zauważmy, że wartości w naszej tablicy wynikowej są posortowane, a więc możemy tu zastosować przeszukiwanie binarne, sprowadzając złożoność do O(nlogn).