Longest Increasing Subsequence

Q: Wie hoch ist die Zeitkomplexität der längsten steigenden Teilsequenz?

Die Tails-Methode benötigt O(n log n) Zeit und O(n) Speicherplatz: eine binäre Suche pro Element. Die dynamische Programmierungstabelle über jedes Indexpaar benötigt O(n²) Zeit, und das Ausprobieren jeder Teilsequenz benötigt O(2ⁿ) . Für n = 2500 sind das etwa 30.000, 3 Millionen und eine astronomische Anzahl von Schritten.

Q: Warum liefert das Patience-Sorting-Verfahren die richtige Länge?

Nach jedem Element enthält tails[k] den kleinsten Wert, mit dem eine bis dahin gefundene aufsteigende Teilsequenz der Länge k+1 enden kann. Ein Anhängen erfolgt nur, wenn x größer als jeder Endwert ist. Das bedeutet, dass nun eine Teilsequenz existiert, die um eins länger ist als jede zuvor gefundene. Das Ersetzen ändert die Länge nie, sondern senkt lediglich einen Endwert. Daher entspricht die Länge der Liste immer der Länge der längsten aufsteigenden Teilsequenz.

Q: Wie erhältst du die tatsächliche längste aufsteigende Teilsequenz und nicht nur ihre Länge?

Speichere für jedes Element einen Vorgänger. In der O(n²) -Tabelle ist der Vorgänger von i das j , das ending[i] seinen Wert gegeben hat. Speichere bei der Tails-Methode den Index des Elements hinter jedem Tail und setze den Vorgänger eines Elements auf den Index, der eine Position links davon gespeichert ist, wenn es eingefügt wird. Gehe dann vom Ende der längsten Teilsequenz aus die Vorgänger zurück und kehre das Ergebnis um.

Q: Wie findest du stattdessen die längste nicht absteigende Teilsequenz?

Gleiche Nachbarn zulassen. Verwende in der Tabelle nums[j] ≤ nums[i] . Suche bei der Tails-Methode nach dem ersten Ende, das strikt größer als x ist, statt nach einem größeren oder gleichen, sodass ein gleicher Wert die Liste erweitert, anstatt ein Ende zu ersetzen. [7, 7, 7, 7] ergibt dann 4.

MittelDynamische Programmierung Binäre Suche

+10

Du erhältst eine Liste von Ganzzahlen nums. Eine Teilsequenz behält einige der Elemente in ihrer ursprünglichen Reihenfolge bei und lässt die übrigen weg; die behaltenen Elemente müssen nicht direkt nebeneinanderstehen. Gib die Länge der längsten Teilsequenz zurück, deren Werte von links nach rechts streng ansteigen. Zwei gleiche aufeinanderfolgende Werte gelten nicht als ansteigend.

Funktion

lengthOfLIS(nums: integer-array) → integer

numsinteger-array: die Liste der Ganzzahlen, aus der ausgewählt werden soll
Gibt zurückinteger: die Länge der längsten streng monoton steigenden Teilfolge

Einschränkungen

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

Beispiele

Eingabe: nums = [3, 1, 8, 2, 5, 9, 4, 7]
Ausgabe: 4
Erklärung: 1, 2, 5, 9 ergeben eine aufsteigende Teilfolge der Länge 4, ebenso 1, 2, 5, 7 und 1, 2, 4, 7. Keine Auswahl von fünf Werten steigt weiter an, also lautet die Antwort 4.

+20 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du eine längste aufsteigende Teilsequenz selbst zurückgeben, nicht nur ihre Länge, und trotzdem in O(n log n)-Zeit laufen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Eine Teilfolge kann beliebige Elemente auslassen, daher gibt es bei einer Liste mit n Zahlen 2^n davon – viel zu viele, um sie alle zu überprüfen. Die Lösung mit dynamischer Programmierung besteht darin, für jeden Index eine engere Frage zu stellen: Wie lang ist die längste aufsteigende Teilfolge, die genau hier endet? Daraus ergibt sich eine Tabelle mit O(n²). Die schnellste Variante speichert für jede Länge eine Zahl: den kleinsten Wert, mit dem eine Teilfolge dieser Länge enden kann, und fügt jedes neue Element mithilfe einer binären Suche ein.

Jedes Element nehmen oder überspringen

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Gehe die Liste durch und triff für jedes Element eine Entscheidung: Behalte es oder lasse es weg. Du darfst nums[i] nur behalten, wenn es größer ist als der letzte Wert, den du behalten hast. Eine rekursive Funktion longest(i, prev) beantwortet die Frage: Wenn das zuletzt beibehaltene Element am Index prev steht (oder bei -1, wenn bisher nichts behalten wurde), wie viele weitere Elemente kannst du ab Index i hinzufügen?

Überspringen ergibt longest(i+1, prev). Behalten ergibt, sofern es erlaubt ist, 1 + longest(i+1, i). Die Antwort ist der größere der beiden Werte, und hinter dem Ende der Liste kann nichts mehr hinzugefügt werden, also ist das Ergebnis dort 0. Jede aufsteigende Teilfolge entspricht einem Pfad aus Entscheidungen zum Behalten und Überspringen, daher kann die Suche die beste Lösung nicht übersehen.

Das ist langsam, weil beide Zweige offen bleiben, wenn die Werte ansteigen. Bei einer Liste wie 1, 2, 3, ..., n verdoppelt sich die Anzahl der Aufrufe mit jedem Element: 2 hoch 40 sind bereits etwa 10^12 Aufrufe, und die großen Tests haben 2500 Elemente. Doch longest(i, prev) hängt nur vom Paar (i, prev) ab, daher gibt es höchstens n² verschiedene Fragen. Jede davon nur einmal zu stellen, ist der nächste Ansatz.

Algorithmus

Schreibe longest(i, prev), wobei prev der Index des zuletzt beibehaltenen Elements ist oder -1.
Wenn i hinter dem Ende liegt, gib 0 zurück.
Überspringe nums[i]: best = longest(i+1, prev).
Wenn prev -1 ist oder nums[i] > nums[prev] gilt, behalte es bei: best = max(best, 1 + longest(i+1, i)).
Gib best zurück. Die Antwort ist 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)

Längste Teilsequenz, die an jedem Index endet

Idee

Zustand. Sei ending[i] die Länge der längsten aufsteigenden Teilfolge, deren letztes Element nums[i] ist. Das Festlegen des letzten Elements macht es möglich, das Problem klar aufzuteilen: Sobald du weißt, wo eine Teilfolge endet, weißt du, welche späteren Werte darauf folgen können.

Rekurrenz. Wenn die bei nums[i] endende Teilfolge mehr als ein Element hat, ist das Element vor nums[i] ein nums[j] mit j < i und nums[j] < nums[i], und der Teil bis zu diesem Element sollte so lang wie möglich sein. Also ist ending[i] = 1 + max(ending[j]) für diese j. Basisfall: Jedes Element für sich ist eine Teilfolge, also beginnt ending[i] bei 1. Reihenfolge: ending[i] greift nur auf kleinere Indizes zu, also füllst du die Tabelle von links nach rechts.

Für [3, 1, 8, 2, 5, 9, 4, 7] lautet die Tabelle [1, 1, 2, 2, 3, 4, 3, 4]. Zum Beispiel kann auf 3, 1 oder 2 eine 5 folgen, und das beste davon ist 2 mit ending = 2, also ist ending[4] = 3. Die Antwort ist der größte Eintrag, 4, nicht der letzte: Die beste Teilfolge kann an beliebiger Stelle enden.

Jeder Index betrachtet jeden früheren Index genau einmal, also beträgt der Aufwand n(n-1)/2 Vergleiche, etwa 3.1 × 10^6 für n = 2500.

Algorithmus

Erstelle ending mit jedem Eintrag auf 1 gesetzt.
Betrachte für jedes i von links nach rechts jedes j < i.
Wenn nums[j] < nums[i] gilt, setze ending[i] auf ending[j] + 1, wenn dieser Wert größer ist.
Gib den größten Wert in ending zurück.

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)

Kleinste Enden mit binärer Suche

Idee

Die obige Tabelle speichert für jeden Index eine Länge. Du kannst weniger speichern: Für jede Länge nur den kleinsten Wert, mit dem eine aufsteigende Teilsequenz dieser Länge enden kann. Nenne ihn tails[k] für die Länge k+1. Ein kleinerer Endwert ist immer mindestens genauso gut, denn jeder Wert, der auf eine Teilsequenz folgen kann, die mit 9 endet, kann auch auf eine folgen, die mit 5 endet.

tails ist immer streng aufsteigend sortiert: Eine Teilsequenz der Länge k+2, die mit t endet, enthält eine Teilsequenz der Länge k+1, die mit einem Wert kleiner als t endet. Führe also für jeden neuen Wert x eine binäre Suche nach dem ersten Endwert durch, der ≥ x ist. Gibt es keinen, ist x größer als jeder Endwert und verlängert die längste Teilsequenz, also hänge ihn an. Andernfalls ersetze diesen Endwert durch x: Die Teilsequenz mit einem Element weniger endet unterhalb von x, sodass das Hinzufügen von x dieselbe Länge mit einem kleineren Endwert ergibt.

Für [3, 1, 8, 2, 5, 9, 4, 7] nimmt tails nacheinander die Werte [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7] an, und seine Länge 4 ist die Antwort. Beim Schritt [1, 2, 4, 9] kam die 4 in der Eingabe nach der 9, daher ist tails selbst keine Teilsequenz; nur seine Länge hat eine Bedeutung. Die Methode wird auch Geduldssortieren genannt, nach dem Kartenspiel, bei dem jeder Endwert die oberste Karte eines Stapels ist.

Jedes Element erfordert eine binäre Suche über höchstens n Endwerte: etwa 2500 × 12 = 30.000 Schritte für die größte Eingabe.

Algorithmus

Beginne mit einer leeren Liste tails.
Führe für jedes x in nums eine binäre Suche nach dem ersten Index k durch, für den tails[k] ≥ x gilt.
Wenn kein Element in tails ≥ x ist, füge x hinzu.
Setze andernfalls tails[k] = x.
Gib die Länge von tails zurück.

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)

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen dadurch, dass man verwechselt, was die Tabelle enthält, oder gleiche Werte als ansteigend behandelt.

ending[n-1] statt des größten Eintrags zurückgeben. Bei [1, 2, 3, 0] ist der letzte Eintrag 1, aber die Antwort ist 3.
Mit ≤ statt < vergleichen. [7, 7, 7, 7] muss 1 zurückgeben, nicht 4.
Bei der tails-Variante nach dem ersten Ende > x statt ≥ x suchen. Bei Duplikaten wird dadurch die zweite 7 nach der ersten angehängt und gleiche Werte werden als längere Teilfolge gezählt.
tails als die Teilfolge selbst behandeln. Die Werte können aus verschiedenen Teilfolgen stammen, also gib sie nur aus, wenn du die Vorgänger separat erfasst.
Aus Versehen die zusammenhängende Variante lösen. Bei [3, 1, 8, 2, 5, 9, 4, 7] ist die längste ansteigende Folge benachbarter Werte 2, 5, 9 (Länge 3), während die Antwort 4 ist.
In Lua und R beginnen Arrays bei 1. Daher wird ein 0-basierter Marker prev = -1 zu 0, und die binäre Suche läuft über die Indizes 1 bis zur aktuellen Größe.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität der längsten steigenden Teilsequenz?

Die Tails-Methode benötigt O(n log n) Zeit und O(n) Speicherplatz: eine binäre Suche pro Element. Die dynamische Programmierungstabelle über jedes Indexpaar benötigt O(n²) Zeit, und das Ausprobieren jeder Teilsequenz benötigt O(2ⁿ). Für n = 2500 sind das etwa 30.000, 3 Millionen und eine astronomische Anzahl von Schritten.

Warum liefert das Patience-Sorting-Verfahren die richtige Länge?

Nach jedem Element enthält tails[k] den kleinsten Wert, mit dem eine bis dahin gefundene aufsteigende Teilsequenz der Länge k+1 enden kann. Ein Anhängen erfolgt nur, wenn x größer als jeder Endwert ist. Das bedeutet, dass nun eine Teilsequenz existiert, die um eins länger ist als jede zuvor gefundene. Das Ersetzen ändert die Länge nie, sondern senkt lediglich einen Endwert. Daher entspricht die Länge der Liste immer der Länge der längsten aufsteigenden Teilsequenz.

Wie erhältst du die tatsächliche längste aufsteigende Teilsequenz und nicht nur ihre Länge?

Speichere für jedes Element einen Vorgänger. In der O(n²)-Tabelle ist der Vorgänger von i das j, das ending[i] seinen Wert gegeben hat. Speichere bei der Tails-Methode den Index des Elements hinter jedem Tail und setze den Vorgänger eines Elements auf den Index, der eine Position links davon gespeichert ist, wenn es eingefügt wird. Gehe dann vom Ende der längsten Teilsequenz aus die Vorgänger zurück und kehre das Ergebnis um.

Wie findest du stattdessen die längste nicht absteigende Teilsequenz?

Gleiche Nachbarn zulassen. Verwende in der Tabelle nums[j] ≤ nums[i]. Suche bei der Tails-Methode nach dem ersten Ende, das strikt größer als x ist, statt nach einem größeren oder gleichen, sodass ein gleicher Wert die Liste erweitert, anstatt ein Ende zu ersetzen. [7, 7, 7, 7] ergibt dann 4.

Python

def lengthOfLIS(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

Longest Increasing Subsequence

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Jedes Element nehmen oder überspringen

Längste Teilsequenz, die an jedem Index endet

Kleinste Enden mit binärer Suche

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben