Longest Increasing Subsequence

Q: Jaka jest złożoność czasowa problemu najdłuższego rosnącego podciągu?

Metoda tails działa w czasie O(n log n) i wymaga O(n) pamięci: jedno wyszukiwanie binarne na element. Tabela obejmująca każdą parę indeksów wymaga O(n²) czasu, a sprawdzenie każdej podsekwencji — O(2ⁿ) .

Q: Jak zamiast tego znaleźć najdłuższy podciąg niemalejący?

Pozwól na równe sąsiednie wartości. W tabeli użyj nums[j] ≤ nums[i] . W metodzie ogonów wyszukaj pierwszy ogon ściśle większy niż x , aby równa wartość wydłużyła listę zamiast zastępować ogon. [7, 7, 7, 7] zwraca wtedy 4.

ŚrednieProgramowanie dynamiczne Wyszukiwanie binarne

+10

Otrzymujesz listę liczb całkowitych nums. Podciąg zachowuje niektóre elementy w ich pierwotnej kolejności, a pozostałe pomija; zachowane elementy nie muszą znajdować się obok siebie. Zwróć długość najdłuższego podciągu, którego wartości ściśle rosną od lewej do prawej. Dwie równe wartości występujące kolejno nie oznaczają wzrostu.

Funkcja

lengthOfLIS(nums: integer-array) → integer

numsinteger-array: lista liczb całkowitych do wyboru
Zwracainteger: długość najdłuższego ściśle rosnącego podciągu

Ograniczenia

1 ≤ nums.length ≤ 2500
-10⁴ ≤ nums[i] ≤ 10⁴

Przykłady

Wejście: nums = [3, 1, 8, 2, 5, 9, 4, 7]
Wyjście: 4
Wyjaśnienie: 1, 2, 5, 9 rośnie, podobnie jak 1, 2, 5, 7 oraz 1, 2, 4, 7: długość 4. Żaden wybór pięciu wartości nie zachowuje rosnącej kolejności.

Pytanie dodatkowe

Czy możesz zwrócić jedną najdłuższą rosnącą podsekwencję wraz z jej długością i nadal działać w czasie O(n log n)?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Lista n liczb ma 2^n podciągów, zdecydowanie zbyt wiele, by je sprawdzić. Ustalenie dla każdego indeksu, jak długa jest najdłuższa rosnąca podsekwencja kończąca się dokładnie w tym miejscu, daje tablicę o rozmiarze O(n²). Najszybsza wersja przechowuje dla każdej długości najmniejszą wartość, którą może mieć na końcu podciąg o tej długości, i umieszcza każdy element za pomocą wyszukiwania binarnego.

Weź każdy element lub go pomiń

Poprawne, ale nie kończy się na największych testach

Intuicja

Zdecyduj dla każdego elementu, czy go zachować; możesz zachować nums[i] tylko wtedy, gdy jest większy od ostatniej zachowanej wartości. longest(i, prev) to największa liczba elementów, które możesz jeszcze dodać, zaczynając od indeksu i, gdy ostatni zachowany element znajduje się pod indeksem prev (lub -1). Pominięcie daje longest(i+1, prev); zachowanie daje 1 + longest(i+1, i). Każdy rosnący podciąg odpowiada jednej ścieżce tych wyborów.

Dla ciągu 1, 2, 3, ..., n obie gałęzie pozostają otwarte, a liczba wywołań podwaja się z każdym elementem: 2^40 to już około 10^12. Istnieje jednak co najwyżej n² różnych par (i, prev).

Algorytm

Napisz longest(i, prev), gdzie prev to indeks ostatniego zachowanego elementu albo -1.
Jeśli i jest poza końcem, zwróć 0.
Pomiń nums[i]: best = longest(i+1, prev).
Jeśli prev wynosi -1 lub nums[i] > nums[prev], zachowaj ten element: best = max(best, 1 + longest(i+1, i)).
Zwróć best. Odpowiedzią jest longest(0, -1).

def lengthOfLIS(nums):
    def longest(i, prev):
        # The longest increasing subsequence of nums[i:] whose values all exceed nums[prev].
        # prev is -1 while nothing has been taken.
        if i == len(nums):
            return 0
        best = longest(i + 1, prev)  # skip nums[i]
        if prev == -1 or nums[i] > nums[prev]:
            best = max(best, 1 + longest(i + 1, i))  # take nums[i]
        return best

    return longest(0, -1)

Najdłuższy podciąg kończący się na każdym indeksie

Intuicja

Niech ending[i] oznacza długość najdłuższego rosnącego podciągu, którego ostatnim elementem jest nums[i]. Element przed nums[i], jeśli istnieje, to pewne nums[j], dla którego j < i i nums[j] < nums[i], a podciąg kończący się na nim powinien być jak najdłuższy. Zatem ending[i] = 1 + max(ending[j]) dla takich j, a jeśli ich nie ma, wartość wynosi 1. Wypełniaj tablicę od lewej do prawej.

Dla [3, 1, 8, 2, 5, 9, 4, 7] tablica wygląda tak: [1, 1, 2, 2, 3, 4, 3, 4]: po 5 może wystąpić 3, 1 lub 2, a najdłuższy z tych podciągów ma długość 2, więc ending[4] = 3. Odpowiedzią jest największa wartość w tablicy, ponieważ najlepszy podciąg może kończyć się w dowolnym miejscu.

n(n-1)/2 porównań: około 3.1 × 10^6 dla n = 2500.

Algorytm

Utwórz ending, ustawiając każdy element na 1.
Dla każdego i, od lewej do prawej, sprawdź każde j < i.
Jeśli nums[j] < nums[i], ustaw ending[i] na ending[j] + 1, jeśli ta wartość jest większa.
Zwróć największą wartość w ending.

def lengthOfLIS(nums):
    n = len(nums)
    # ending[i]: the longest increasing subsequence that ends with nums[i]
    ending = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i] and ending[j] + 1 > ending[i]:
                ending[i] = ending[j] + 1
    return max(ending)

Najmniejsze ogony przy użyciu wyszukiwania binarnego

Intuicja

Dla każdej długości zachowuj tylko najmniejszą wartość, którą może kończyć się rosnący podciąg tej długości: tails[k] dla długości k+1. Mniejsze zakończenie nigdy nie jest gorsze: po 9 może wystąpić wszystko, co może wystąpić po 5. tails pozostaje ściśle rosnące: usuń ostatnią wartość rosnącego podciągu długości k+2, a otrzymasz podciąg długości k+1, który kończy się mniejszą wartością.

Dla każdego x wyszukaj binarnie pierwszą wartość w tails, która jest ≥ x. Jeśli jej nie ma, dopisz x: wydłuża on najdłuższy podciąg. W przeciwnym razie zastąp tę wartość przez x: podciąg krótszy o jeden kończy się wartością mniejszą niż x, więc x daje tę samą długość z mniejszą wartością końcową.

Na przykładzie 1 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]: długość 4. W [1, 2, 4, 9] wartość 4 występuje po 9, więc znaczenie ma tylko długość tails.

Algorytm

Zacznij od pustej listy tails.
Dla każdego x w nums wyszukaj binarnie pierwszy indeks k, dla którego tails[k] ≥ x.
Jeśli żaden ogon nie jest ≥ x, dołącz x.
W przeciwnym razie ustaw tails[k] = x.
Zwróć długość tails.

from bisect import bisect_left


def lengthOfLIS(nums):
    # tails[k]: the smallest last value of any increasing subsequence of length k + 1
    tails = []
    for x in nums:
        k = bisect_left(tails, x)  # the first tail that is >= x
        if k == len(tails):
            tails.append(x)  # x extends the longest subsequence so far
        else:
            tails[k] = x  # x is a smaller ending for length k + 1
    return len(tails)

Pułapki i przypadki brzegowe

Zwracanie ending[n-1] zamiast największego elementu. Dla [1, 2, 3, 0] ostatni element to 1, ale odpowiedzią jest 3.
Porównywanie z ≤ zamiast z <. Dla [7, 7, 7, 7] wynikiem musi być 1, a nie 4.
W wersji z ogonami wyszukiwanie pierwszego ogona > x zamiast ≥ x. Druga 7 zostaje wtedy dołączona za pierwszą, przez co równe wartości są liczone jako rosnące.
Przypadkowe rozwiązanie wersji dotyczącej ciągłych podciągów. W przykładzie 1 najdłuższy rosnący ciąg sąsiadujących elementów to 2, 5, 9 (długość 3), podczas gdy odpowiedzią jest 4.
Pozostawianie indeksów liczonych od 0 w Lua lub R, gdzie tablice zaczynają się od 1. Znacznik prev = -1 staje się równy 0, a wyszukiwanie binarne obejmuje indeksy od 1 do bieżącego rozmiaru.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu najdłuższego rosnącego podciągu?

Metoda tails działa w czasie O(n log n) i wymaga O(n) pamięci: jedno wyszukiwanie binarne na element. Tabela obejmująca każdą parę indeksów wymaga O(n²) czasu, a sprawdzenie każdej podsekwencji — O(2ⁿ).

Czym jest sortowanie cierpliwości w problemie najdłuższego rosnącego podciągu?

To metoda stosu kart, której nazwa pochodzi od gry karcianej. Każdy stos to karta na szczycie stosu kart: karta trafia na stos położony najbardziej na lewo, którego wierzchnia karta ma wartość co najmniej taką jak ona, albo rozpoczyna nowy stos. Odpowiedzią jest liczba stosów.

Jak zamiast tego znaleźć najdłuższy podciąg niemalejący?

Pozwól na równe sąsiednie wartości. W tabeli użyj nums[j] ≤ nums[i]. W metodzie ogonów wyszukaj pierwszy ogon ściśle większy niż x, aby równa wartość wydłużyła listę zamiast zastępować ogon. [7, 7, 7, 7] zwraca wtedy 4.

def lengthOfLIS(nums):
    # Wpisz tutaj kod

Test #1

Test #2

Test #3

Argument

nums = [3, 1, 8, 2, 5, 9, 4, 7]

Oczekiwany wynik

Longest Increasing Subsequence

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Weź każdy element lub go pomiń

Najdłuższy podciąg kończący się na każdym indeksie

Najmniejsze ogony przy użyciu wyszukiwania binarnego

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania