Longest Increasing Subsequence
Du erhältst eine Liste von Ganzzahlen nums. Eine Teilfolge behält einige der Elemente in ihrer ursprünglichen Reihenfolge bei und lässt die übrigen weg; die behaltenen Elemente müssen nicht direkt nebeneinander stehen. Gib die Länge der längsten Teilfolge zurück, deren Werte von links nach rechts streng ansteigen. Zwei gleiche Werte hintereinander gelten nicht als ansteigend.
Funktion
- numsinteger-array
- die Liste der Ganzzahlen, aus denen ausgewählt werden soll
- Gibt zurückinteger
- die Länge der längsten streng monoton steigenden Teilfolge
Einschränkungen
1 ≤ nums.length ≤ 2500-104 ≤ nums[i] ≤ 104
Beispiele
- Eingabe
- nums = [3, 1, 8, 2, 5, 9, 4, 7]
- Ausgabe
- 4
- Erklärung
- 1, 2, 5, 9 steigt, und genauso 1, 2, 5, 7 und 1, 2, 4, 7: Länge 4. Keine Auswahl von fünf Werten bleibt steigend.
- Eingabe
- nums = [7, 7, 7, 7]
- Ausgabe
- 1
- Erklärung
- Die Werte müssen streng ansteigen, daher können keine zwei der 7er in derselben Teilfolge sein. Ein einzelnes Element zählt bereits, daher ist die Antwort 1.
- Eingabe
- nums = [12, -4, 0, 25, -10, 3, 16, 5]
- Ausgabe
- 4
- Erklärung
- -4, 0, 3, 16 hat die Länge 4. Beginnend mit dem ersten Element, 12, erhältst du nur zwei Werte, zum Beispiel 12, 25: Die beste Teilfolge muss nicht am Anfang beginnen.
Weiterführende Frage
Kannst du eine längste aufsteigende Teilsequenz selbst zusammen mit ihrer Länge zurückgeben und trotzdem in O(n log n) Zeit arbeiten?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Die beste Teilfolge der gesamten Liste lässt sich nur schwer direkt beschreiben. Stelle für jeden Index
ieine engere Frage: Was ist die längste aufsteigende Teilfolge, die genau mitnums[i]endet?Eine Teilsequenz, die bei
nums[i]endet, besteht entweder nur ausnums[i]oder setzt die beste Teilsequenz fort, die bei einem früherennums[j] < nums[i]endet. Wähle das beste solchejund addiere eins. Die Antwort ist der größte dieser Werte, unabhängig davon, wo die Teilsequenz endet.Um unter
O(n²)zu kommen, speicherst du für jede Länge nur den kleinsten Wert, mit dem eine Teilfolge dieser Länge enden kann. Diese Werte bleiben sortiert, sodass eine binäre Suche dir sagt, ob eine neue Zahl die längste Teilfolge verlängert oder einen Endwert ersetzt.
Lösung
Eine Liste mit n Zahlen hat 2^n Teilfolgen – viel zu viele, um sie alle zu prüfen. Fragt man für jeden Index, wie lang die beste auf genau dort endende aufsteigende Teilfolge ist, erhält man eine Tabelle mit O(n²). Die schnellste Variante speichert für jede Länge den kleinsten Wert, mit dem eine Teilfolge dieser Länge enden kann, und fügt jedes Element mithilfe einer binären Suche ein.
Jedes Element nehmen oder überspringen
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Entscheide für jedes Element, ob du es behältst; du darfst nums[i] nur behalten, wenn es größer als der zuletzt behaltene Wert ist. longest(i, prev) ist die maximale Anzahl von Elementen, die du ab dem Index i noch hinzufügen kannst, wenn das zuletzt behaltene Element bei prev steht (oder -1). Beim Überspringen ergibt sich longest(i+1, prev); beim Behalten ergibt sich 1 + longest(i+1, i). Jede aufsteigende Teilfolge entspricht einem Pfad dieser Entscheidungen.
Bei 1, 2, 3, ..., n bleiben beide Zweige offen und die Anzahl der Aufrufe verdoppelt sich mit jedem Element: 2^40 sind bereits etwa 10^12. Es gibt jedoch höchstens n² verschiedene Paare (i, prev).
Algorithmus
- Schreibe
longest(i, prev), wobeiprevder Index des letzten beibehaltenen Elements oder-1ist. - Wenn
ihinter dem Ende liegt, gib 0 zurück. - Überspringe
nums[i]:best = longest(i+1, prev). - Wenn
prev-1ist odernums[i] > nums[prev]gilt, behalte es bei:best = max(best, 1 + longest(i+1, i)). - Gib
bestzurück. Die Antwort istlongest(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
Sei ending[i] die Länge der längsten aufsteigenden Teilsequenz, deren letztes Element nums[i] ist. Das Element vor nums[i], falls vorhanden, ist 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 gilt ending[i] = 1 + max(ending[j]) für diese j oder 1, wenn es keine gibt. Fülle die Werte von links nach rechts aus.
Für [3, 1, 8, 2, 5, 9, 4, 7] lautet die Tabelle [1, 1, 2, 2, 3, 4, 3, 4]: Auf 5 kann 3, 1 oder 2 folgen, und die beste dieser Möglichkeiten hat die Länge 2, also ending[4] = 3. Die Antwort ist der größte Eintrag, da die beste Teilsequenz an beliebiger Stelle enden kann.
n(n-1)/2 Vergleiche: etwa 3.1 × 10^6 für n = 2500.
Algorithmus
- Erstelle
ending, wobei jeder Eintrag auf 1 gesetzt ist. - Betrachte für jedes
ivon links nach rechts jedesj < i. - Wenn
nums[j] < nums[i]gilt, setzeending[i]aufending[j] + 1, wenn dieser Wert größer ist. - Gib den größten Wert in
endingzurü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
Für jede Länge behalten wir nur den kleinsten Wert, mit dem eine aufsteigende Teilsequenz dieser Länge enden kann: tails[k] für die Länge k+1. Ein kleinerer Endwert ist nie schlechter: Alles, was auf eine 9 folgen kann, kann auch auf eine 5 folgen. tails bleibt streng aufsteigend: Entfernt man den letzten Wert einer aufsteigenden Teilsequenz der Länge k+2, erhält man eine Teilsequenz der Länge k+1, die mit einem kleineren Wert endet.
Für jedes x suchen wir binär nach dem ersten Endwert ≥ x. Gibt es keinen, hängen wir x an: So wird die längste Teilsequenz verlängert. Andernfalls ersetzen wir diesen Endwert durch x: Die um eins kürzere Teilsequenz endet unterhalb von x, also ergibt x dieselbe Länge mit einem kleineren Endwert.
Zum Beispiel 1 entwickelt sich tails zu [3], [1], [1, 8], [1, 2], [1, 2, 5], [1, 2, 5, 9], [1, 2, 4, 9], [1, 2, 4, 7]: Länge 4. In [1, 2, 4, 9] kam die 4 nach der 9, daher hat nur die Länge von tails eine Bedeutung.
Algorithmus
- Beginne mit einer leeren Liste
tails. - Führe für jedes
xinnumseine binäre Suche nach dem ersten Indexkmittails[k] ≥ xdurch. - Wenn kein Element in
tails≥ xist, fügexhinzu. - Andernfalls setze
tails[k] = x. - Gib die Länge von
tailszurü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
ending[n-1]zurückgeben, statt des größten Eintrags. Bei[1, 2, 3, 0]ist der letzte Eintrag 1, aber die Antwort ist 3.- Mit
≤statt mit<vergleichen.[7, 7, 7, 7]muss 1 zurückgeben, nicht 4. - In der tails-Variante nach dem ersten Tail
> xstatt nach≥ xsuchen. Die zweite 7 wird dann nach der ersten angehängt, sodass gleiche Werte als aufsteigend gezählt werden. - Aus Versehen die zusammenhängende Variante lösen. In Beispiel 1 ist die längste aufsteigende Folge benachbarter Elemente 2, 5, 9 (Länge 3), während die Antwort 4 ist.
- In Lua oder R 0-basierte Indizes beibehalten, obwohl Arrays bei 1 beginnen. Der Marker
prev = -1wird zu 0, und die binäre Suche läuft über die Indizes 1 bis zur aktuellen Größe.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität der längsten aufsteigenden Teilfolge?
Die tails-Methode benötigt O(n log n) Zeit und O(n) Speicherplatz: eine binäre Suche pro Element. Die Tabelle über jedes Indexpaar benötigt O(n²) Zeit, und das Ausprobieren jeder Teilfolge benötigt O(2ⁿ).
Was ist Geduldssortierung bei der längsten aufsteigenden Teilsequenz?
Es ist die nach einem Kartenspiel benannte Tails-Methode. Jeder Stapel wird durch seine oberste Karte repräsentiert: Eine Karte kommt auf den ganz linken Stapel, dessen oberste Karte mindestens ihren Wert hat, oder beginnt einen neuen Stapel. Die Anzahl der Stapel ist die Antwort.
Wie findest du stattdessen die längste nicht abnehmende Teilsequenz?
Gleiche Nachbarn sind erlaubt. Verwende in der Tabelle nums[j] ≤ nums[i]. Suche bei der Tails-Methode nach dem ersten Ende, das strikt größer als x ist, sodass ein gleicher Wert die Liste verlängert, statt ein Ende zu ersetzen. [7, 7, 7, 7] gibt dann 4 zurück.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def lengthOfLIS(nums):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argument
nums = [3, 1, 8, 2, 5, 9, 4, 7]
Erwartete Ausgabe
4