algorithm
Längst ökande efterföljande

Längst ökande efterföljande grundläggande information

Det längsta ökande efterföljdsproblemet är att hitta efterföljande från givinmatningssekvensen i vilken efterföljande element sorteras i lägsta till högsta ordning. All efterföljd är inte sammanhängande eller unik.

Tillämpning av längsta ökande efterföljande:

Algoritmer som Längst ökar efterföljd, Längsta vanliga efterföljande används i versionskontrollsystem som Git och etc.

Enkel form av algoritm:

1. Hitta unika rader som är gemensamma för båda dokumenten.
2. Ta alla sådana rader från det första dokumentet och beställ dem efter utseende i det andra dokumentet.
3. Beräkna LIS för den resulterande sekvensen (genom att göra en Patience Sort ), få den längsta matchande sekvensen av rader, en korrespondens mellan raderna i två dokument.
4. Återvinn algoritmen på varje rad av rader mellan redan matchade.

Låt oss nu överväga ett enklare exempel på LCS-problemet. Här är ingången bara en sekvens av distinkta heltal a1,a2,...,an. , och vi vill hitta den längsta ökande efterföljelsen i den. Till exempel, om ingången är 7,3,8,4,2,6, är den längsta ökande efterföljden 3,4,6 .

Det enklaste tillvägagångssättet är att sortera inmatningselement i ökande ordning och tillämpa LCS-algoritmen på de ursprungliga och sorterade sekvenserna. Men om du tittar på den resulterande matrisen kommer du att märka att många värden är desamma, och matrisen ser mycket upprepade ut. Detta antyder att LIS-problemet (längst ökande efterföljande) kan göras med dynamisk programmeringsalgoritm med endast en-dimensionell matris.

Pseudokod:

1. Beskriv en mängd värden vi vill beräkna.
   För 1 <= i <= n , låt A (i) vara längden på den längsta ökande ingångssekvensen. Observera att längden vi till slut är intresserad av är max{A(i)|1 ≤ i ≤ n} .
2. Ge en återfall.
   För 1 <= i <= n , A(i) = 1 + max{A(j)|1 ≤ j < i och input(j) < input(i)}.
3. Beräkna värdena på A.
4. Hitta den optimala lösningen.

Följande program använder A för att beräkna en optimal lösning. Den första delen beräknar ett värde m så att A (m) är längden på en optimal ökande efterföljande ingång. Den andra delen beräknar ett optimalt ökande efterföljande, men för enkelhets skull skriver vi ut det i omvänd ordning. Detta program körs i tid O (n), så hela algoritmen körs i tid O (n ^ 2).

Del 1:

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

Del 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

Rekursiv lösning:

Tillvägagångssätt 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

Tidskomplexitet i tillvägagångssätt 1: O(n*2^n)

Tillvägagångssätt 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], ∞)

Tidskomplexitet i tillvägagångssätt 2: O(n^2)

Tillvägagångssätt 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])

Tidskomplexitet i tillvägagångssätt 3: O(n^2)

Iterativ algoritm:

Beräknar värden iterativt nedifrån och upp.

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

Tidskomplexitet i itterativ metod: O(n^2)

Hjälprum: O(n)

Låter ta {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} som ingång. Så den längsta ökande efterföljden för den givna ingången är {0, 2, 6, 9, 11, 15} .

C # Implementering

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