algorithm
Najdłuższa rosnąca kolejność

Najdłużej rosnące kolejne sekwencje Podstawowe informacje

Problemem najdłuższej narastającej sekwencji jest znalezienie podsekwencji z podanej sekwencji wejściowej, w której elementy podsekwencji są sortowane w kolejności od najniższej do najwyższej. Wszystkie podsekwencje nie są ciągłe ani niepowtarzalne.

Zastosowanie najdłuższej rosnącej kolejności:

Algorytmy takie jak najdłuższa rosnąca sekwencja, najdłuższa wspólna sekwencja są używane w systemach kontroli wersji, takich jak Git itp.

Prosta forma algorytmu:

1. Znajdź unikalne linie wspólne dla obu dokumentów.
2. Weź wszystkie takie wiersze z pierwszego dokumentu i uporządkuj je zgodnie z ich wyglądem w drugim dokumencie.
3. Oblicz LIS wynikowej sekwencji (wykonując sortowanie cierpliwości ), uzyskując najdłuższą pasującą sekwencję wierszy, zgodność między wierszami dwóch dokumentów.
4. Ponownie wykonaj algorytm dla każdego zakresu linii między już dopasowanymi.

Rozważmy teraz prostszy przykład problemu LCS. Tutaj wejście jest tylko jedną sekwencją różnych liczb całkowitych a1,a2,...,an. , i chcemy znaleźć w niej najdłuższy rosnący podciąg. Na przykład, jeśli dane wejściowe wynoszą 7,3,8,4,2,6, najdłużej rosnąca podsekwencja wynosi 3,4,6 .

Najłatwiejszym sposobem jest sortowanie elementów wejściowych w kolejności rosnącej i zastosowanie algorytmu LCS do oryginalnych i posortowanych sekwencji. Jeśli jednak spojrzysz na wynikową tablicę, zauważysz, że wiele wartości jest takich samych, a tablica wygląda bardzo powtarzalnie. Sugeruje to, że problem LIS (najdłużej rosnącego podsekwencji) można rozwiązać za pomocą algorytmu programowania dynamicznego wykorzystującego tablicę jednowymiarową.

Pseudo kod:

1. Opisz tablicę wartości, które chcemy obliczyć.
   Dla 1 <= i <= n , niech A (i) będzie długością najdłuższej wzrastającej sekwencji wejściowej. Zauważ, że długość, którą ostatecznie jesteśmy zainteresowani, wynosi max{A(i)|1 ≤ i ≤ n} .
2. Daj powtórkę.
   Dla 1 <= i <= n , A(i) = 1 + max{A(j)|1 ≤ j < i i input(j) < input(i)}.
3. Oblicz wartości A.
4. Znajdź optymalne rozwiązanie.

Poniższy program używa A do obliczenia optymalnego rozwiązania. Pierwsza część oblicza wartość m taką, że A (m) jest długością optymalnie rosnącej podsekwencji wejściowej. Druga część oblicza optymalną rosnącą podsekwencję, ale dla wygody drukujemy ją w odwrotnej kolejności. Ten program działa w czasie O (n), więc cały algorytm działa w czasie O (n ^ 2).

Część 1:

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

Część 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

Rozwiązanie rekurencyjne:

Podejście 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

Złożoność czasowa w podejściu 1: O(n*2^n)

Podejście 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], ∞)

Złożoność czasowa w podejściu 2: O(n^2)

Podejście 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])

Złożoność czasowa w podejściu 3: O(n^2)

Algorytm iteracyjny:

Oblicza wartości iteracyjnie w sposób oddolny.

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

Złożoność czasowa w podejściu iteracyjnym: O(n^2)

Przestrzeń pomocnicza: O(n)

Weźmy {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} jako dane wejściowe. Zatem najdłuższa rosnąca kolejność dla danych wejściowych wynosi {0, 2, 6, 9, 11, 15} .

Implementacja C #

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);
    }
}