algorithm
La subsecuencia cada vez mayor

La información básica de la subsecuencia cada vez más creciente

El problema de la Subsecuencia Cada vez mayor más larga es encontrar la subsecuencia de la secuencia de entrada de ingreso en la que los elementos de la subsecuencia se ordenan de menor a mayor orden. Todas las subsecuencias no son contiguas o únicas.

Aplicación de la subsecuencia creciente más larga:

Algoritmos como la Subsecuenciación Más Larga, la Subsecuencia Común Más Larga se utilizan en los sistemas de control de versiones como Git y etc.

Forma simple de algoritmo:

1. Encuentra líneas únicas que son comunes a ambos documentos.
2. Tome todas las líneas del primer documento y ordénelas de acuerdo con su aspecto en el segundo documento.
3. Calcule el LIS de la secuencia resultante (haciendo una Clasificación de Paciencia ), obteniendo la secuencia de líneas más larga, una correspondencia entre las líneas de dos documentos.
4. Recurse el algoritmo en cada rango de líneas entre los ya emparejados.

Ahora consideremos un ejemplo más simple del problema LCS. Aquí, la entrada es solo una secuencia de enteros distintos a1,a2,...,an. , y queremos encontrar la subsecuencia creciente más larga en ella. Por ejemplo, si la entrada es 7,3,8,4,2,6 , la subsecuencia de mayor crecimiento es 3,4,6 .

El enfoque más sencillo es ordenar los elementos de entrada en orden creciente y aplicar el algoritmo LCS a las secuencias originales y ordenadas. Sin embargo, si observa la matriz resultante, notará que muchos valores son iguales, y la matriz parece muy repetitiva. Esto sugiere que el problema de LIS (la subsecuencia en aumento más larga) se puede hacer con el algoritmo de programación dinámica utilizando solo una matriz unidimensional.

Pseudo Código:

1. Describe una matriz de valores que queremos calcular.
   Para 1 <= i <= n , sea A (i) la longitud de una secuencia de entrada cada vez más larga. Tenga en cuenta que la longitud que nos interesa en última instancia es la max{A(i)|1 ≤ i ≤ n} .
2. Dar una recurrencia.
   Para 1 <= i <= n , A(i) = 1 + max{A(j)|1 ≤ j < i y input(j) < input(i)}.
3. Calcula los valores de A.
4. Encuentra la solución óptima.

El siguiente programa usa A para calcular una solución óptima. La primera parte calcula un valor m tal que A (m) es la longitud de una subsecuencia de entrada en aumento óptima. La segunda parte calcula una subsecuencia creciente óptima, pero por conveniencia lo imprimimos en orden inverso. Este programa se ejecuta en el tiempo O (n), por lo que todo el algoritmo se ejecuta en el tiempo 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

Solución recursiva:

Enfoque 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 complejidad del tiempo en el Enfoque 1: O(n*2^n)

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

Complejidad de tiempo en el enfoque 2: O(n^2)

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

Complejidad de tiempo en el enfoque 3: O(n^2)

Algoritmo iterativo:

Calcula los valores de forma iterativa de manera ascendente.

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 complejidad del tiempo en el enfoque iterativo: O(n^2)

Espacio auxiliar: O(n)

Permite tomar {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} como entrada. Por lo tanto, la Subsecuencia creciente más larga para la entrada dada es {0, 2, 6, 9, 11, 15} .

Implementación de 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);
    }
}