Wir haben eine Matrix mit $n$ Zahlen: $a$.Die Aufgabe ist, die längste, streng aufsteigende Teilfolge in $a$ zu finden.

Formell suchen wir die längste Folge von Indizes $i_1, \Punkte i_k$, so dass$$$i_1 < i_2 < \Punkte < i_k,\\\a < a < \Punkte < a$$

In diesem Artikel besprechen wir mehrere Algorithmen zur Lösung dieser Aufgabe und diskutieren einige andere Probleme, die auf dieses Problem reduziert werden können.

Lösung in $O(n^2)$ mit dynamischer Programmierung

Die dynamische Programmierung ist eine sehr allgemeine Technik, die es erlaubt, eine große Klasse von Problemen zu lösen, die wir hier auf unsere spezielle Aufgabe anwenden.

Zunächst werden wir nur nach der Länge der längsten ansteigenden Teilfolge suchen und erst später lernen, wie man die Teilfolge selbst wiederherstellt.

Finden der Länge

Um diese Aufgabe zu lösen, definieren wir ein Array $d$, wobei $d$ die Länge der längsten ansteigenden Teilfolge ist, die in dem Element mit dem Index $i$ endet.Wir berechnen dieses Array schrittweise: erst $d$, dann $d$ usw. Nachdem dieses Array berechnet ist, ist die Antwort auf die Aufgabe der maximale Wert im Array $d$.

So sei der aktuelle Index $i$.D.h. wir wollen den Wert $d$ berechnen und alle vorherigen Werte $d, \dots, d$ sind bereits bekannt.Dann gibt es zwei Möglichkeiten:

• $d = 1$: die gewünschte Teilfolge besteht nur aus dem Element $a$.
• $d > 1$: dann befindet sich in der geforderten Teilfolge eine weitere Zahl vor der Zahl $a$.Konzentrieren wir uns auf diese Zahl:es kann ein beliebiges Element $a$ sein mit $j = 0 \Punkte i-1$ und $a < a$.Auf diese Weise können wir $d$ mit der folgenden Formel berechnen:Wenn wir den Index $j$ fixieren, dann hat die längste aufsteigende Teilfolge, die in den beiden Elementen $a$ und $a$ endet, die Länge $d + 1$.Alle diese Werte $d$ sind bereits bekannt, so dass wir $d$ direkt berechnen können mit:$$d = \max_{\substack{j = 0 \dots i-1 \\ a < a}} \left(d + 1\right)$$

Wenn wir diese beiden Fälle kombinieren, erhalten wir die endgültige Antwort für $d$:

$$d = \max\left(1, \max_{\substack{j = 0 \dots i-1 \\\ a < a}} \left(d + 1\right)\right)$$

Implementierung

Hier ist eine Implementierung des oben beschriebenen Algorithmus, der die Länge der längsten ansteigenden Teilfolge berechnet.

int lis(vector<int> const& a) { int n = a.size(); vector<int> d(n, 1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a < a) d = max(d, d + 1); } } int ans = d; for (int i = 1; i < n; i++) { ans = max(ans, d); } return ans;}

Wiederherstellen der Teilfolge

Bis jetzt haben wir nur gelernt, wie man die Länge der Teilfolge findet, aber nicht, wie man die Teilfolge selbst findet.

Um die Teilfolge wiederherstellen zu können, erzeugen wir ein zusätzliches Hilfsarray $p$, das wir neben dem Array $d$ berechnen.$p$ ist der Index $j$ des vorletzten Elements in der längsten aufsteigenden Teilfolge, die mit $i$ endet.Mit anderen Worten ist der Index $p$ derselbe Index $j$, bei dem der höchste Wert $d$ erhalten wurde.Dieses Hilfsarray $p$ weist in gewisser Weise auf die Vorfahren hin.

Um dann die Unterfolge abzuleiten, beginnen wir einfach bei dem Index $i$ mit dem maximalen $d$, und folgen den Vorfahren, bis wir die gesamte Unterfolge abgeleitet haben, d.h. bis wir das Element mit $d = 1$ erreichen.

Implementierung der Wiederherstellung

Wir werden den Code aus den vorherigen Abschnitten ein wenig ändern.Wir werden neben $d$ auch das Array $p$ berechnen und anschließend die Teilfolge berechnen.

Der Einfachheit halber weisen wir den Vorfahren ursprünglich $p = -1$ zu.Für Elemente mit $d = 1$ bleibt der Wert der Vorfahren $-1$, was für die Wiederherstellung der Teilfolge etwas bequemer ist.

vector<int> lis(vector<int> const& a) { int n = a.size(); vector<int> d(n, 1), p(n, -1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a < a && d < d + 1) { d = d + 1; p = j; } } } int ans = d, pos = 0; for (int i = 1; i < n; i++) { if (d > ans) { ans = d; pos = i; } } vector<int> subseq; while (pos != -1) { subseq.push_back(a); pos = p; } reverse(subseq.begin(), subseq.end()); return subseq;}

Alternativer Weg zur Wiederherstellung der Teilfolge

Es ist auch möglich, die Teilfolge ohne das Hilfsarray $p$ wiederherzustellen.Wir können einfach den aktuellen Wert von $d$ neu berechnen und auch sehen, wie das Maximum erreicht wurde.

Diese Methode führt zu einem etwas längeren Code, aber im Gegenzug sparen wir etwas Speicher.

Lösung in $O(n \log n)$ mit dynamischer Programmierung und binärer Suche

Um eine schnellere Lösung für das Problem zu erhalten, konstruieren wir eine andere Lösung mit dynamischer Programmierung, die in $O(n^2)$ abläuft, und verbessern sie später auf $O(n \log n)$.

Wir werden das Array $d$ der dynamischen Programmierung verwenden.Diesmal ist $d$ das Element, an dem eine Teilfolge der Länge $i$ endet.

Wenn es mehrere solcher Folgen gibt, dann nehmen wir diejenige, die im kleinsten Element endet.

Anfänglich nehmen wir $d = -\infty$ und für alle anderen Elemente $d = \infty$.

Wir werden wieder schrittweise die Zahlen abarbeiten, zuerst $a$, dann $a$ usw., und in jedem Schritt das Array $d$ so pflegen, dass es aktuell ist.

Nach der Abarbeitung aller Elemente von $a$ ist die Länge der gewünschten Teilfolge das größte $l$ mit $d < \infty$.

int lis(vector<int> const& a) { int n = a.size(); const int INF = 1e9; vector<int> d(n+1, INF); d = -INF; for (int i = 0; i < n; i++) { for (int j = 1; j <= n; j++) { if (d < a && a < d) d = a; } } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

Wir machen nun zwei wichtige Beobachtungen.

Das Array $d$ wird immer sortiert sein: $d \le d$ für alle $i = 1 \Punkte n$.Und auch das Element $a$ wird höchstens einen Wert $d$ aktualisieren.

Damit können wir dieses Element im Array $d$ mittels binärer Suche in $O(\log n)$ finden.Tatsächlich suchen wir im Array $d$ einfach nach der ersten Zahl, die strikt größer als $a$ ist, und versuchen, dieses Element auf die gleiche Weise zu aktualisieren wie bei der obigen Implementierung.

Implementierung

int lis(vector<int> const& a) { int n = a.size(); const int INF = 1e9; vector<int> d(n+1, INF); d = -INF; for (int i = 0; i < n; i++) { int j = upper_bound(d.begin(), d.end(), a) - d.begin(); if (d < a && a < d) d = a; } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

Wiederherstellung der Teilfolge

Auch mit diesem Ansatz ist es möglich, die Teilfolge wiederherzustellen.Diesmal müssen wir zwei Hilfsmatrizen führen: eine, die uns den Index der Elemente in $d$ angibt, und eine „Vorfahren“-Matrix $p$. $p$ ist der Index des vorherigen Elements der optimalen Teilfolge, die mit dem Element $i$ endet.

Es ist einfach, diese beiden Matrizen im Laufe der Iteration über die Matrix $a$ neben den Berechnungen von $d$ zu führen.Und am Ende ist es nicht schwer, die gewünschte Teilfolge mit Hilfe dieser Arrays wiederherzustellen.

Lösung in $O(n \log n)$ mit Datenstrukturen

Anstelle der obigen Methode zur Berechnung der längsten ansteigenden Teilfolge in $O(n \log n)$ können wir das Problem auch auf eine andere Weise lösen: mit Hilfe einiger einfacher Datenstrukturen.

Kehren wir zur ersten Methode zurück und erinnern uns, dass $d$ der Wert $d + 1$ mit $j < i$ und $a < a$ ist.

Wenn wir also ein zusätzliches Array $t$ definieren, so dass $$t] = d,$$dann ist das Problem der Berechnung des Wertes $d$ äquivalent dazu, den maximalen Wert in einem Präfix des Arrays $t$ zu finden:$$d = \\left(t – 1] + 1\right)$$

Das Problem, das Maximum eines Präfixes eines Arrays (das sich ändert) zu finden, ist ein Standardproblem, das durch viele verschiedene Datenstrukturen gelöst werden kann. Zum Beispiel können wir einen Segmentbaum oder einen Fenwick-Baum verwenden.

Diese Methode hat natürlich einige Nachteile: in Bezug auf die Länge und die Komplexität der Implementierung wird dieser Ansatz schlechter sein als die Methode mit binärer Suche.Außerdem, wenn die Eingabezahlen $a$ besonders groß sind, dann müssten wir einige Tricks anwenden, wie die Zahlen zu komprimieren (d.h. sie von $0$ auf $n-1$ umzunummerieren), oder einen impliziten Segmentbaum zu verwenden (nur die Zweige des Baumes zu erzeugen, die wichtig sind).Andernfalls wird der Speicherverbrauch zu hoch.

Auf der anderen Seite hat diese Methode auch einige Vorteile:Man muss sich bei dieser Methode keine Gedanken über irgendwelche kniffligen Eigenschaften in der Lösung der dynamischen Programmierung machen.Und dieser Ansatz erlaubt es uns, das Problem sehr einfach zu verallgemeinern (siehe unten).

Verwandte Aufgaben

Hier sind mehrere Probleme, die eng mit dem Problem der Suche nach der längsten steigenden Teilfolge verwandt sind.

Längste nicht-abnehmende Teilfolge

Das ist eigentlich fast das gleiche Problem, nur dass man jetzt gleiche Zahlen in der Teilfolge verwenden darf.

Die Lösung ist im Grunde auch fast die gleiche.Wir müssen nur die Ungleichheitszeichen ändern und die binäre Suche leicht modifizieren.

Anzahl der längsten steigenden Teilfolgen

Wir können die zuerst besprochene Methode verwenden, entweder die $O(n^2)$-Version oder die Version mit Datenstrukturen.Wir müssen nur zusätzlich speichern, auf wie viele Arten wir längste aufsteigende Teilfolgen erhalten können, die auf die Werte $d$ enden.

Die Anzahl der Möglichkeiten, eine längste aufsteigende Teilfolge zu bilden, die auf $a$ endet, ist die Summe aller Möglichkeiten für alle längsten aufsteigenden Teilfolgen, die auf $j$ enden, wobei $d$ maximal ist.Es kann mehrere solcher $j$ geben, so dass wir alle summieren müssen.

Unter Verwendung eines Segmentbaums kann dieser Ansatz auch in $O(n \log n)$ implementiert werden.

Es ist nicht möglich, den binären Suchansatz für diese Aufgabe zu verwenden.

Kleinste Anzahl nicht-aufsteigender Teilfolgen, die eine Folge abdecken

Für ein gegebenes Array mit $n$ Zahlen $a$ müssen wir die Zahlen in der kleinsten Anzahl von Farben einfärben, so dass jede Farbe eine nicht-aufsteigende Teilfolge bildet.

Um dies zu lösen, stellen wir fest, dass die minimale Anzahl der benötigten Farben gleich der Länge der längsten steigenden Teilfolge ist.

Beweis:Wir müssen die Dualität dieser beiden Probleme beweisen.

Bezeichnen wir mit $x$ die Länge der längsten aufsteigenden Teilfolge und mit $y$ die kleinste Anzahl von nicht aufsteigenden Teilfolgen, die eine Überdeckung bilden.

Wir müssen beweisen, dass $x = y$ ist.

Es ist klar, dass $y < x$ nicht möglich ist, denn wenn wir $x$ streng aufsteigende Elemente haben, dann können keine zwei davon Teil der gleichen nicht aufsteigenden Teilfolge sein.Daher haben wir $y \ge x$.

Wir zeigen nun, dass $y > x$ durch Widerspruch nicht möglich ist.Nehmen wir an, dass $y > x$.Dann betrachten wir eine beliebige optimale Menge von $y$ nicht-steigenden Teilfolgen.Wir transformieren diese Menge auf folgende Weise: Solange es zwei solche Teilfolgen gibt, so dass die erste vor der zweiten Teilfolge beginnt und die erste Folge mit einer Zahl größer oder gleich der zweiten beginnt, lösen wir diese Startzahl und hängen sie an den Anfang der zweiten an.Nach einer endlichen Anzahl von Schritten haben wir $y$ Teilfolgen, und ihre Anfangszahlen bilden eine aufsteigende Teilfolge der Länge $y$.Da wir angenommen haben, dass $y > x$ ist, sind wir zu einem Widerspruch gelangt.

Daraus folgt, dass $y = x$.

Wiederherstellung der Sequenzen:Die gewünschte Aufteilung der Sequenz in Teilsequenzen kann gierig erfolgen, d.h. man geht von links nach rechts und ordnet die aktuelle Zahl oder die Teilsequenz zu, die mit der minimalen Zahl endet, die größer oder gleich der aktuellen Zahl ist.

Praxisprobleme

• Topcoder – IntegerSequence
• Topcoder – AutoMarket
• Codeforces – Tourist
• Codeforces – LCIS
• SPOJ – SUPPER
• Topcoder – BridgeArrangement
• ACMSGURU – „Nord-Ost“