algorithm
Langst stijgende volgorde

Langst stijgende vervolg basisinformatie

Het probleem met de langst stijgende volgorde is het vinden van de reeks in de invoerreeks waarin de elementen van de reeks in de laagste tot de hoogste volgorde worden gesorteerd. Alle deelreeksen zijn niet aaneengesloten of uniek.

Toepassing van de langst stijgende volgorde:

Algoritmen zoals de langst stijgende volgordes, de langste gangbare volgordes worden gebruikt in versiecontrolesystemen zoals Git en enz.

Eenvoudige vorm van algoritme:

1. Zoek unieke regels die beide documenten gemeen hebben.
2. Neem al deze regels uit het eerste document en rangschik ze volgens hun uiterlijk in het tweede document.
3. Bereken het LIS van de resulterende reeks (door een Patience Sort uit te voeren ), waarbij u de langste overeenkomende reeks regels krijgt, een overeenkomst tussen de regels van twee documenten.
4. Verzorg het algoritme op elk lijnbereik tussen reeds overeenkomende lijnen.

Laten we nu een eenvoudiger voorbeeld van het LCS-probleem bekijken. Hier is invoer slechts één reeks afzonderlijke gehele getallen a1,a2,...,an. , en we willen er de langst toenemende deelreeks in vinden. Indien bijvoorbeeld ingang 7,3,8,4,2,6 dan de langste toenemende subsequentie 3,4,6.

De eenvoudigste aanpak is om invoerelementen in oplopende volgorde te sorteren en het LCS-algoritme op de oorspronkelijke en gesorteerde sequenties toe te passen. Als u echter naar de resulterende array kijkt, ziet u dat veel waarden hetzelfde zijn en dat de array er erg repetitief uitziet. Dit suggereert dat het LIS-probleem (langste toenemende deelreeks) kan worden opgelost met een dynamisch programmeeralgoritme dat alleen een eendimensionale array gebruikt.

Pseudo-code:

1. Beschrijf een reeks waarden die we willen berekenen.
   Voor 1 <= i <= n , laat A (i) de lengte zijn van een langst toenemende reeks invoer. Merk op dat de lengte waarin we uiteindelijk geïnteresseerd zijn, max{A(i)|1 ≤ i ≤ n} .
2. Geef een herhaling.
   Voor 1 <= i <= n , A(i) = 1 + max{A(j)|1 ≤ j < i en input(j) < input(i)}.
3. Bereken de waarden van A.
4. Vind de optimale oplossing.

Het volgende programma gebruikt A om een optimale oplossing te berekenen. Het eerste deel berekent een waarde m zodanig dat A (m) de lengte is van een optimale toenemende deelreeks invoer. Het tweede deel berekent een optimale toenemende deelreeks, maar voor het gemak drukken we het in omgekeerde volgorde af. Dit programma wordt uitgevoerd in tijd O (n), dus het hele algoritme wordt uitgevoerd in tijd O (n ^ 2).

Deel 1:

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

Deel 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

Recursieve oplossing:

Benadering 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

Tijdcomplexiteit in Benadering 1: O(n*2^n)

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

Tijdcomplexiteit in aanpak 2: O(n^2)

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

Tijdcomplexiteit in aanpak 3: O(n^2)

Iteratief algoritme:

Berekent de waarden iteratief in bottom-up mode.

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

Tijdcomplexiteit in Iteratieve benadering: O(n^2)

Hulpruimte: O(n)

Laten we {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} nemen als invoer. Dus is de langst stijgende vervolgvolgorde voor de gegeven invoer {0, 2, 6, 9, 11, 15} .

C # Implementatie

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