Längste aufsteigende Teilfolge
O(n^2)-DP und anschließend der O(n log n)-Trick
Längste aufsteigende Teilfolge ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was eine LIS ist
Eine Teilfolge behält die Reihenfolge bei, lässt aber Elemente aus. Die längste aufsteigende Teilfolge ist die längste solche Folge, die streng ansteigt.
a = [3, 1, 4, 1, 5, 9, 2]Teilfolge statt Teilarray
Anders als ein Teilarray muss eine LIS nicht zusammenhängend sein. Sie können kleinere Zahlen überspringen, damit die Kette weiter wächst.
Der DP-Zustand für O(n^2)
Sei dp[i] die Länge der LIS, die bei Index i endet. Jedes Element bildet für sich genommen mindestens eine Teilfolge der Länge eins.
dp = [1] * nDer Übergang für O(n^2)
Betrachten Sie für jedes i jedes frühere j. Wenn a[j] kleiner ist, erweitern Sie die Folge: dp[i] = max(dp[i], dp[j] + 1).
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)Das Ergebnis ablesen
Das Ergebnis ist der größte Wert in der Tabelle, da die LIS an beliebiger Stelle enden kann, nicht nur am letzten Index.
answer = max(dp)Warum O(n^2) zum Zeitlimit führt
Die doppelte Schleife benötigt O(n^2). Für n nahe 100000 ist das viel zu langsam und führt zu einem Zeitlimit-Ergebnis.
Die Idee hinter Patience Sorting
Die schnellere Methode verwaltet für jede Teilfolgenlänge eine Liste mit dem kleinstmöglichen Endwert, ähnlich wie beim Patience Sorting.
tails = []Mit bisect platzieren
Führen Sie für jede Zahl mit bisect_left eine binäre Suche nach der passenden Position unter den Endwerten durch. So ergibt sich insgesamt O(n log n).
from bisect import bisect_leftErweitern oder ersetzen
Liegt die Position hinter dem Ende, verwenden Sie append, um die LIS zu verlängern. Andernfalls überschreiben Sie diesen Endwert mit dem kleineren Wert.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xDie Länge steckt in tails
Wenn der Durchlauf endet, ist len(tails) die Länge der LIS. Die Liste selbst ist nicht immer die Teilfolge; nur ihre Länge ist exakt.
answer = len(tails)Streng aufsteigend oder nicht fallend
Für eine nicht fallende Variante wechseln Sie zu bisect_right, damit gleiche Werte die Kette verlängern können.
from bisect import bisect_rightSchnelltest
Welche Methode findet die LIS-Länge in O(n log n)?
Zusammenfassung: Von n^2 zu n log n
Sie können LIS jetzt auf zwei Arten lösen. Die O(n^2)-DP ist einfach; die Methode mit Endwerten und bisect skaliert für große Eingaben und hält das Zeitlimit ein.
Häufig gestellte Fragen
Ist die Lektion „Längste aufsteigende Teilfolge“ kostenlos?
Ja — der vollständige Text von „Längste aufsteigende Teilfolge“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Längste aufsteigende Teilfolge“?
O(n^2)-DP und anschließend der O(n log n)-Trick Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Längste aufsteigende Teilfolge“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Memoization oder Tabulation
- Zustand und Übergang definieren
- Treppensteigen und Münzkombinationen
- Längste aufsteigende Teilfolge