algorithm
Plus longue sous-séquence croissante

Information de base sur la sous-séquence croissante la plus longue

Le problème de la sous-séquence croissante la plus longue consiste à trouver la sous-séquence à partir de la séquence d'entrée de la sous-séquence dans laquelle les éléments de la sous-séquence sont classés par ordre croissant . Toutes les sous-séquences ne sont ni contiguës ni uniques.

Application de la plus longue sous-séquence croissante:

Des algorithmes tels que la sous-séquence croissante la plus longue, la sous-séquence commune la plus longue sont utilisés dans les systèmes de contrôle de version tels que Git, etc.

Forme simple de l'algorithme:

1. Trouvez des lignes uniques communes aux deux documents.
2. Prenez toutes ces lignes du premier document et commandez-les en fonction de leur apparence dans le deuxième document.
3. Calculez le LIS de la séquence résultante (en effectuant un tri de patience ), en obtenant la séquence de lignes correspondant le plus longtemps, une correspondance entre les lignes de deux documents.
4. Reconstruire l'algorithme sur chaque plage de lignes entre celles déjà correspondantes.

Considérons maintenant un exemple plus simple du problème de LCS. Ici, input n'est qu'une séquence d'entiers distincts a1,a2,...,an. , et nous voulons y trouver la sous-séquence croissante la plus longue. Par exemple, si l’entrée est 7,3,8,4,2,6 alors la plus longue sous-séquence croissante est 3,4,6 .

L'approche la plus simple consiste à trier les éléments d'entrée dans un ordre croissant et à appliquer l'algorithme LCS aux séquences d'origine et aux séquences triées. Cependant, si vous regardez le tableau résultant, vous remarquerez que de nombreuses valeurs sont identiques et que le tableau est très répétitif. Cela suggère que le problème de LIS (sous-séquence augmentant le plus longtemps) peut être résolu avec un algorithme de programmation dynamique utilisant uniquement un tableau à une dimension.

Pseudo Code:

1. Décrivez un tableau de valeurs que nous voulons calculer.
   Pour 1 <= i <= n , soit A (i) la longueur d'une plus longue séquence d'entrées croissante. Notez que la longueur à laquelle nous sommes finalement intéressés est max{A(i)|1 ≤ i ≤ n} .
2. Donner une récurrence.
   Pour 1 <= i <= n , A(i) = 1 + max{A(j)|1 ≤ j < i et input(j) < input(i)}.
3. Calculer les valeurs de A.
4. Trouvez la solution optimale.

Le programme suivant utilise A pour calculer une solution optimale. La première partie calcule une valeur m telle que A (m) est la longueur d'une sous-séquence croissante optimale d'entrée. La seconde partie calcule une sous-séquence croissante optimale, mais pour plus de commodité, nous l'imprimons dans l'ordre inverse. Ce programme s'exécute dans le temps O (n), donc tout l'algorithme s'exécute dans le temps O (n ^ 2).

Partie 1:

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

Partie 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

Solution récursive:

Approche 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

La complexité temporelle dans l'approche 1: O(n*2^n)

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

Complexité temporelle en approche 2: O(n^2)

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

Complexité temporelle en approche 3: O(n^2)

Algorithme itératif:

Calcule les valeurs itérativement de manière ascendante.

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

La complexité temporelle dans l'approche itérative: O(n^2)

Espace auxiliaire: O(n)

Prenons en entrée {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} . Donc, la plus longue sous-séquence croissante pour l'entrée donnée est {0, 2, 6, 9, 11, 15} .

Implémentation 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);
    }
}