algorithm
Längste zunehmende Folge

Am längsten wachsende Teilsequenz Basisinformationen

Das am längsten zunehmende Untersequenzproblem besteht darin, aus der gegebenen Eingabesequenz eine Untersequenz zu finden, in der die Elemente der Untersequenz in der niedrigsten bis höchsten Reihenfolge sortiert sind. Alle Untersequenzen sind nicht zusammenhängend oder eindeutig.

Anwendung der am längsten wachsenden Teilfolge:

Algorithmen wie die am längsten wachsende Teilfolge, die längste häufigste Teilfolge werden in Versionskontrollsystemen wie Git und usw. verwendet.

Einfache Form des Algorithmus:

1. Finden Sie eindeutige Zeilen, die beiden Dokumenten gemeinsam sind.
2. Nehmen Sie alle derartigen Zeilen aus dem ersten Dokument und ordnen Sie sie entsprechend ihrem Aussehen im zweiten Dokument.
3. Berechnen Sie das LIS der resultierenden Sequenz (durch Ausführen einer Patience-Sortierung ), und erhalten Sie die längste übereinstimmende Zeilenfolge sowie eine Entsprechung zwischen den Zeilen zweier Dokumente.
4. Rekurse den Algorithmus für jeden Zeilenbereich zwischen bereits übereinstimmenden Zeilen.

Betrachten wir nun ein einfacheres Beispiel für das LCS-Problem. Die Eingabe ist hier nur eine Folge verschiedener ganzer Zahlen a1,a2,...,an. und wir wollen die am längsten wachsende Teilsequenz darin finden. Wenn zum Beispiel die Eingabe 7,3,8,4,2,6 ist, dann ist die am längsten zunehmende Untersequenz 3,4,6 .

Am einfachsten ist es, die Eingangselemente in aufsteigender Reihenfolge zu sortieren und den LCS-Algorithmus auf die ursprünglichen und sortierten Sequenzen anzuwenden. Wenn Sie jedoch das resultierende Array betrachten, werden Sie feststellen, dass viele Werte gleich sind und das Array sehr wiederholend wirkt. Dies legt nahe, dass das LIS-Problem (longest zunehmende Teilsequenz) mit einem dynamischen Programmieralgorithmus unter Verwendung nur eines eindimensionalen Arrays gelöst werden kann.

Pseudo-Code:

1. Beschreiben Sie ein Array von Werten, die wir berechnen möchten.
   Für 1 <= i <= n sei A (i) die Länge einer am längsten zunehmenden Eingabesequenz. Beachten Sie, dass die Länge, an der wir letztendlich interessiert sind, max{A(i)|1 ≤ i ≤ n} .
2. Geben Sie eine Wiederholung an.
   Für 1 <= i <= n gilt A(i) = 1 + max{A(j)|1 ≤ j < i und der input(j) < input(i)}.
3. Berechnen Sie die Werte von A.
4. Finden Sie die optimale Lösung.

Das folgende Programm verwendet A, um eine optimale Lösung zu berechnen. Der erste Teil berechnet einen Wert m so, dass A (m) die Länge einer optimal ansteigenden Teilfolge der Eingabe ist. Der zweite Teil berechnet eine optimal ansteigende Teilsequenz, druckt diese jedoch aus Gründen der Vereinfachung in umgekehrter Reihenfolge aus. Dieses Programm läuft in der Zeit O (n), der gesamte Algorithmus läuft in der Zeit O (n ^ 2).

Teil 1:

m ← 1 
for i : 2..n 
    if A(i) > A(m) then 
        m ← i 
    end if 
end for

Teil 2:

put a
while A(m) > 1 do 
    i ← m−1 
    while not(ai < am and A(i) = A(m)−1) do 
        i ← i−1 
    end while 
    m ← i 
    put a
 end while

Rekursive Lösung:

Ansatz 1:

LIS(A[1..n]):
    if (n = 0) then return 0
    m = LIS(A[1..(n − 1)])
    B is subsequence of A[1..(n − 1)] with only elements less than a[n]
    (* let h be size of B, h ≤ n-1 *)
    m = max(m, 1 + LIS(B[1..h]))
    Output m

Zeitkomplexität in Ansatz 1: O(n*2^n)

Ansatz 2:

LIS(A[1..n], x):
    if (n = 0) then return 0
    m = LIS(A[1..(n − 1)], x)
    if (A[n] < x) then
        m = max(m, 1 + LIS(A[1..(n − 1)], A[n]))
    Output m

MAIN(A[1..n]):
    return LIS(A[1..n], ∞)

Zeitkomplexität in Ansatz 2: O(n^2)

Ansatz 3:

LIS(A[1..n]):
    if (n = 0) return 0
    m = 1
    for i = 1 to n − 1 do
        if (A[i] < A[n]) then
            m = max(m, 1 + LIS(A[1..i]))
    return m

MAIN(A[1..n]):
    return LIS(A[1..i])

Zeitkomplexität in Ansatz 3: O(n^2)

Iterativer Algorithmus:

Berechnet die Werte iterativ auf Bottom-Up-Weise.

LIS(A[1..n]):
    Array L[1..n]
    (* L[i] = value of LIS ending(A[1..i]) *)
    for i = 1 to n do
        L[i] = 1
        for j = 1 to i − 1 do
            if (A[j] < A[i]) do
                L[i] = max(L[i], 1 + L[j])
    return L

MAIN(A[1..n]):
    L = LIS(A[1..n])
        return the maximum value in L

Zeitkomplexität im iterativen Ansatz: O(n^2)

Hilfsraum: O(n)

Nehmen wir {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} als Eingabe. Die am längsten zunehmende Teilsequenz für die gegebene Eingabe ist also {0, 2, 6, 9, 11, 15} .

C # -Implementierung

public class LongestIncreasingSubsequence
{
    private static int Lis(int[] input, int n)
    {
        int[] lis = new int[n];
        int max = 0;
        for(int i = 0; i < n; i++)
        {
            lis[i] = 1;
        }
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (input[i] > input[j] && lis[i] < lis[j] + 1)
                    lis[i] = lis[j] + 1;
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (max < lis[i])
                max = lis[i];
        }
        return max;
    }

    public static int Main(int[] input)
    {
        int n = input.Length;
        return Lis(input, n);
    }
}