Längste Aufsteigende Teilfolge

Das Ziel des Algorithmus ist es, die längste Teilfolge in einem Array zu finden, welche kontinuierlich aufsteigt.

Im Array $A=[2,13,17,9,11,4,78,28,15,25,99]$ ist die längste aufsteigende Teilfolge (LAT) z.B.
$LAT=2,9,11,15,25,99$ und hat die Länge $6$.

Gegeben ist dem Algorithmus ein Array $A[1,\dots ,n]$ von Integern und es wird angenommen, das kein Wert doppelt im Array ist.

Gesucht ist die längste aufsteigende Teilfolge wie am Beispiel oben illustriert.

Ansatz mit dynamischer Programmierung

Versuch 1

Beim Versuch 1 wird für $LAT(i)$ immer die längste AT von $A[1,\dots ,i]$ verwendet.

Beispiel

$A=[1,2,5,3,4]$
Das Array $A$ hat die folgenden LATs:

$LAT(1)=1$
$LAT(2)=1,2$
$LAT(3)=1,2,5$
$LAT(4)=1,2,5$
$LAT(5)=1,2,3,4$

Das Problem tritt hier zwischen $LAT(4)$ und $LAT(5)$ auf. Dieser Schritt ist mit Rekursion nicht bzw. nur schwer zu implementieren.

Versuch 2

Versuch 2 geht ähnlich vor, wie dies auch schon in Versuch 1 der Fall war. Allerdings merkt man sich beim zweiten Versuch alle Endungen einer LAT in $A[1,\dots ,i]$.

Beispiel

$A=[1,8,9,5,6,7]$

$LAT(1)=1$
$LAT(2)=1,8$
$LAT(3)=1,8,9$ (eindeutig)
$LAT(4)=1,8,9$ (eindeutig)
$LAT(5)=1,8,9\text{ und }1,5,6$

Auch hier ist dies nur schwer mit Rekursion zu implementieren.

Versuch 3

Die Idee bei Versuch 3 ist, dass man sich auch kürzere ATs in $A[1,\dots ,i]$ merkt.

$E(i,l)$ ist also definiert, als “Es gibt eine AT der Länge $l$, die in Position $i$ endet”. $E(i,l)$ gibt entweder $1$ zurück wenn die AT in $i$ endet oder $0$ wenn sie es nicht tut.

Die Rekursion sieht dann für $l\ge 2$ folgendermassen aus:

$$E(i,l)=\{\begin{array}{ll}1,& \text{falls es }j<i\text{ gibt mit }E(j,l-1)=1\\ & \text{und }A[j]<A[i]\\ 0,& \text{sonst}\end{array}$$

Der Basisfall lautet hier folgendermassen:
$E(i,1)=1$ für alle $i\in \{1,\dots ,n\}$

Laufzeitanalyse

$O({\sum }_{l=1}^n{\sum }_{i=1}^n(i-1))\le O({\sum }_{l=1}^n\frac{n(n-1)}{2})\le O(n^3)$

Wenn man sich die LATs noch einmal anschaut, so sieht man, dass es immer sinnvoller ist, die Folge $1,5,6$ zu verwenden und nicht $1,8,9$. Denn jedes Element, mit welchem man die Folge $1,8,9$ fortsetzen kann, setzt auch die Folge $1,5,6$ fort. Hingegen können Elemente, welche $>6$ aber $<9$ sind noch an die Folge $1,5,6$ angefügt werden, jedoch nicht an $1,8,9$.

Versuch 4

Der vierte Versuch macht sich genau das oben beobachtete zu Nutzen und soll so die Laufzeit verbessern.

$M(i,l)$ ist die kleinstmögliche Endung einer AT der Länge $l$ in $A[1,\dots ,i]$. Falls keine solche AT existiert wird dafür $\infty$ geschrieben.

Die Rekursion sieht dann für $l\ge 2$ folgendermassen aus:

$$M(i,l)=\{\begin{array}{ll}A[i],& \text{falls }M(i-1,l-1)<A[i]<M(i-1,l)\\ M(i-1,l),& \text{sonst}\end{array}$$

Die beiden Basisfälle lauten:

$$M(1,l)=\{\begin{array}{ll}A[1],& l=1\\ \infty ,& l>1\end{array}$$

Hier ist nun eine Laufzeit von $O(n^2)$ möglich.

Beispiel

$A=[1,8,9,5,6,7]$

Auch hier kann man wieder einige Eigenschaften entdecken, welche die Implementierung noch einmal verbessern:

• Die Zeilen sind immer sortiert.
• Pro Zeile wird immer maximal ein Wert geändert.
• Der Wert, welcher geändert werden muss kann mit der Binären Suche in $O(\log (n))$ durchgeführt werden.
• Wenn für jede Zeile dasselbe Array verwendet wird und die Einträge nur überschrieben werden, dauert das Update einer Zeile nur $O(\log (n))$
• Bei $n$ Zeilen kommt man somit auf eine Gesamtlaufzeit von $O(n\log (n)$

Wenn man nun die Elemente der LAT haben möchte, so muss man für jedes Element des Arrays den Vorgänger speichern. Wichtig ist, dass es der Vorgänger zum Zeitpunkt des Einfügen dieses Elementes ist.