- Wird gefüllt
- Wird gelesen
- Ergebnis
Längste aufsteigende Teilfolge (LIS)
Wie viele Zahlen aus einer Liste können Sie auswählen, ohne ihre Reihenfolge zu ändern, sodass jede größer ist als die vorige? Die längste aufsteigende Teilfolge beantwortet diese Frage. Geben Sie eine Liste ein und sehen Sie zu, wie die dynamische Programmierung für jede Position die längste Kette bestimmt, die dort endet. Drücken Sie Abspielen, um zuzusehen, wie sich die Tabelle füllt, oder Schritt und Zurück, um Schritt für Schritt vorzugehen. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Geben Sie eine Liste von Zahlen ein. Für jede Position enthält die Tabelle die Länge der längsten aufsteigenden Kette von Werten, die dort endet, und die frühere Position, an die sie anschließt. Aktivieren Sie Gleiche Werte erlauben für Ketten, die nie fallen. Am Ende wird die Kette von ihrem letzten Wert aus zurückgelesen. Neues Beispiel erzeugt eine andere Liste. Wenn das Feld ausgewählt ist, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Geben Sie eine Liste von Zahlen ein, getrennt durch Kommas oder Leerzeichen. Aktivieren Sie Gleiche Werte erlauben für Ketten, die nie fallen.
- Drücken Sie Abspielen, oder gehen Sie mit Schritt und Zurück Schritt für Schritt vor. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen.
- Sehen Sie zu, wie jede Position mit allen früheren verglichen wird, und sehen Sie dann die längste Kette in Orange zurückgelesen.
So funktioniert die Tabelle
Die Tabelle hat drei Zeilen: die Werte, die Länge der längsten aufsteigenden Teilfolge, die an jeder Position endet, und die Position, an die sie anschließt. Ein Wert allein ist eine Kette der Länge 1. Dann wird jede frühere Position geprüft: Ist ihr Wert kleiner, kann die Kette, die dort endet, um diesen Wert verlängert werden, und ihre Länge wächst um eins. Die längste solche Verlängerung gewinnt, und ihre Position kommt in die dritte Zeile.
Die Kette zurücklesen
Die längste aufsteigende Teilfolge endet an der Position mit der größten Länge. Von dort sagt die dritte Zeile, welche Position davor kommt, und deren dritte Zeile sagt, welche davor kommt, bis zu einer Position ohne Vorgänger. In der richtigen Reihenfolge gelesen, sind diese Werte die Lösung. Ist Gleiche Werte erlauben aktiviert, darf ein Wert auch auf einen gleichen folgen; das ergibt die längste Kette, die nie fällt.
Häufig gestellte Fragen
Was ist der Unterschied zwischen einer Teilfolge und einem Teilarray?
Ein Teilarray ist ein Block benachbarter Werte. Eine Teilfolge behält die Reihenfolge bei, darf aber Werte überspringen. In 3, 10, 2, 1, 20 bilden also 3, 10 und 20 eine aufsteigende Teilfolge, obwohl 2 und 1 dazwischen stehen.
Wie schnell ist der LIS-Algorithmus?
Das Tabellenverfahren vergleicht jedes Paar von Positionen: n·(n − 1)/2 Vergleiche für n Werte. Patience Sorting schafft es in O(n log n): Es merkt sich für jede Länge den kleinsten Wert, der eine Kette dieser Länge beendet, und platziert jeden neuen Wert durch binäre Suche.
Ist die längste aufsteigende Teilfolge eindeutig?
Nicht immer. In 1, 3, 2, 4 haben sowohl 1, 3, 4 als auch 1, 2, 4 die Länge 3. Die Tabelle liefert die Länge, und das Zurücklesen findet eine davon.
Wo wird die längste aufsteigende Teilfolge verwendet?
Beim Vergleichen von Dateien und Genomen, wo manche Verfahren zuerst übereinstimmende Zeilen finden und dann eine aufsteigende Teilfolge ihrer Positionen nehmen; bei Planungsaufgaben und Rätseln zum Stapeln von Kisten; und in der Mathematik, wo die Länge der LIS einer zufälligen Mischung ein berühmter Forschungsgegenstand ist.
Werden Daten irgendwohin gesendet?
Nein. Alles wird in Ihrem Browser berechnet, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor