algorithm
Il più lungo aumento successivo

Informazioni di base sulla successiva più lunga crescita

Il problema di Subsequence crescente più lungo consiste nel trovare una sottosequenza dalla sequenza di input give in cui gli elementi della sottosequenza sono ordinati nell'ordine dal più basso al più alto. Tutte le sottosequenze non sono contigue o uniche.

Applicazione della più lunga Successione crescente:

Algoritmi come il più lungo aumento della successiva, il più lungo termine secondario sono usati nei sistemi di controllo delle versioni come Git e così via.

Forma semplice di algoritmo:

1. Trova linee uniche comuni a entrambi i documenti.
2. Prendi tutte queste righe dal primo documento e ordinale in base al loro aspetto nel secondo documento.
3. Calcola il LIS della sequenza risultante (eseguendo un Patience Sort ), ottenendo la sequenza di righe di corrispondenza più lunga, una corrispondenza tra le righe di due documenti.
4. Recurse l'algoritmo su ogni intervallo di linee tra quelle già abbinate.

Consideriamo ora un esempio più semplice del problema LCS. Qui, l'input è solo una sequenza di interi distinti a1,a2,...,an. e vogliamo trovare la sottosezione crescente più lunga in esso. Ad esempio, se l'input è 7,3,8,4,2,6, la sottosequenza crescente più lunga è 3,4,6 .

L'approccio più semplice è quello di ordinare gli elementi di input in ordine crescente e applicare l'algoritmo LCS alle sequenze originali e ordinate. Tuttavia, se si guarda l'array risultante si noterà che molti valori sono gli stessi e l'array sembra molto ripetitivo. Questo suggerisce che il problema del LIS (il più lungo aumento della sottosequenza) può essere fatto con un algoritmo di programmazione dinamica usando solo un array monodimensionale.

Codice Pseudo:

1. Descrivi una serie di valori che vogliamo calcolare.
   Per 1 <= i <= n , sia A (i) la lunghezza di una sequenza di input crescente più lunga. Si noti che la lunghezza alla quale ci interessiamo alla fine è max{A(i)|1 ≤ i ≤ n} .
2. Dare una ricorrenza.
   Per 1 <= i <= n , A(i) = 1 + max{A(j)|1 ≤ j < i e input(j) < input(i)}.
3. Calcola i valori di A.
4. Trova la soluzione ottimale.

Il seguente programma utilizza A per calcolare una soluzione ottimale. La prima parte calcola un valore m tale che A (m) sia la lunghezza di una sottosequenza crescente ottimale di input. La seconda parte calcola una sottosequenza crescente ottimale, ma per praticità la stampiamo in ordine inverso. Questo programma viene eseguito nel tempo O (n), quindi l'intero algoritmo viene eseguito nel tempo O (n ^ 2).

Parte 1:

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

Parte 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

Soluzione ricorsiva:

Approccio 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

Complessità temporale in Approach 1: O(n*2^n)

Approccio 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], ∞)

Complessità temporale nell'approccio 2: O(n^2)

Approccio 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])

Complessità temporale nell'approccio 3: O(n^2)

Algoritmo iterativo:

Calcola i valori in modo iterativo in modo bottom-up.

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

Complessità temporale nell'approccio iterativo: O(n^2)

Spazio ausiliario: O(n)

Prendiamo {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} come input. Quindi, l'incremento più lungo della sottomissione per l'input dato è {0, 2, 6, 9, 11, 15} .

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