Longest Increasing Subsequence

Przejdź przez listę i podejmij jedną decyzję dla każdego elementu: zachować go czy pominąć. Możesz zachować nums[i] tylko wtedy, gdy jest większy od ostatniej zachowanej wartości. Funkcja rekurencyjna longest(i, prev) odpowiada na pytanie: jeśli ostatni zachowany element znajduje się pod indeksem prev (lub -1, gdy nie zachowano jeszcze żadnego elementu), ile kolejnych elementów możesz dodać, zaczynając od indeksu i?

Pominięcie daje longest(i+1, prev). Zachowanie elementu, gdy jest dozwolone, daje 1 + longest(i+1, i). Odpowiedzią jest większa z tych dwóch wartości. Po dojściu do końca listy nie można już nic dodać, więc wynik wynosi 0. Każdy rosnący podciąg odpowiada jednej ścieżce decyzji o zachowaniu lub pominięciu elementów, więc wyszukiwanie nie może przeoczyć najlepszego rozwiązania.

To rozwiązanie jest powolne, ponieważ obie gałęzie pozostają otwarte, gdy wartości rosną. Na liście takiej jak 1, 2, 3, ..., n liczba wywołań podwaja się z każdym elementem: 2 do potęgi 40 to już około 10^12 wywołań, a duże testy zawierają 2500 elementów. Jednak longest(i, prev) zależy tylko od pary (i, prev), więc istnieje co najwyżej n² różnych pytań. Następnym podejściem jest zadanie każdego z nich tylko raz.

Stan. Niech ending[i] oznacza długość najdłuższego rosnącego podciągu, którego ostatnim elementem jest nums[i]. Ustalenie ostatniego elementu sprawia, że problem można łatwo podzielić: gdy wiesz, gdzie kończy się podciąg, wiesz, jakie późniejsze wartości mogą po nim wystąpić.

Rekurencja. Jeśli podciąg kończący się na nums[i] ma więcej niż jeden element, elementem poprzedzającym nums[i] jest pewne nums[j], dla którego j < i i nums[j] < nums[i], a podciąg kończący się na tym elemencie powinien być jak najdłuższy. Zatem ending[i] = 1 + max(ending[j]) dla takich j. Przypadek bazowy: każdy element sam w sobie jest podciągiem, więc początkowo ending[i] ma wartość 1. Kolejność: ending[i] odczytuje tylko mniejsze indeksy, więc wypełniaj tablicę od lewej do prawej.

Dla [3, 1, 8, 2, 5, 9, 4, 7] tablica ma postać [1, 1, 2, 2, 3, 4, 3, 4]. Na przykład przed 5 może wystąpić 3, 1 lub 2, a najlepszy z tych podciągów kończy się na 2 i ma ending = 2, więc ending[4] = 3. Odpowiedzią jest największa wartość w tablicy, czyli 4, a nie jej ostatni element: najlepszy podciąg może kończyć się w dowolnym miejscu.

Każdy indeks sprawdza po kolei wszystkie wcześniejsze indeksy, więc łączna liczba porównań wynosi n(n-1)/2, czyli około 3.1 × 10^6 dla n = 2500.

Powyższa tabela zapamiętuje jedną długość dla każdego indeksu. Możesz zapamiętywać mniej: dla każdej długości tylko najmniejszą wartość, którą może kończyć się rosnący podciąg o tej długości. Oznaczmy ją jako tails[k] dla długości k+1. Mniejsze zakończenie jest zawsze co najmniej równie dobre, ponieważ każda wartość, która może wystąpić po podciągu kończącym się na 9, może też wystąpić po podciągu kończącym się na 5.

tails jest zawsze posortowane ściśle rosnąco: podciąg o długości k+2 kończący się na t zawiera podciąg o długości k+1, który kończy się wartością mniejszą niż t. Dlatego dla każdej nowej wartości x wyszukaj binarnie pierwszy ogon, który jest ≥ x. Jeśli go nie ma, x jest większe od każdego ogona i wydłuża najdłuższy podciąg, więc dopisz je na końcu. W przeciwnym razie zastąp ten ogon przez x: podciąg krótszy o jeden element kończy się wartością mniejszą niż x, więc dodanie x daje tę samą długość z mniejszą wartością końcową.

Dla [3, 1, 8, 2, 5, 9, 4, 7] tails przyjmuje kolejno wartości [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7], a jego długość 4 jest odpowiedzią. Na etapie [1, 2, 4, 9] wartość 4 pojawiła się w danych wejściowych po 9, więc tails samo w sobie nie jest podciągiem; znaczenie ma tylko jego długość. Metoda ta jest również nazywana sortowaniem cierpliwościowym, od gry karcianej, w której każdy ogon jest wierzchnią kartą stosu.

Każdy element wymaga jednego wyszukiwania binarnego wśród co najwyżej n ogonów: około 2500 × 12 = 30 000 kroków dla największego wejścia.