algorithm
Самая продолжительная подпоследовательность

Самая длинная нарастающая базовая информация

Задача « Самая длинная нарастающая подпоследовательность» заключается в том, чтобы найти подпоследовательность из входной последовательности give, в которой элементы подпоследовательности отсортированы в младшем и высоком порядке. Все подпоследовательности не являются непрерывными или уникальными.

Применение наиболее долговременной последовательности:

Алгоритмы, такие как Longest Increasing Subsequence, Longest Common Subsequence, используются в системах контроля версий, таких как Git и т. Д.

Простая форма алгоритма:

1. Найдите уникальные строки, общие для обоих документов.
2. Возьмите все такие строки из первого документа и закажите их в соответствии со своим внешним видом во втором документе.
3. Вычислите LIS результирующей последовательности (сделав терпение Сортировка ), получив самую длинную совпадающую последовательность строк, соответствие между строками двух документов.
4. Учтите алгоритм для каждого диапазона строк между уже согласованными.

Теперь рассмотрим более простой пример проблемы LCS. Здесь ввод представляет собой только одну последовательность различных целых чисел a1,a2,...,an. , и мы хотим найти в нем самую длинную возрастающую подпоследовательность. Например, если вход 7,3,8,4,2,6, то самая длинная возрастающая подпоследовательность составляет 3,4,6 .

Самый простой способ - сортировать входные элементы в порядке возрастания и применять алгоритм LCS к исходным и отсортированным последовательностям. Однако, если вы посмотрите на результирующий массив, вы заметите, что многие значения одинаковы, и массив выглядит очень повторяющимся. Это говорит о том, что проблема LIS (самая длинная возрастающая подпоследовательность) может быть выполнена с помощью алгоритма динамического программирования, использующего только одномерный массив.

Псевдокод:

1. Опишите массив значений, которые мы хотим вычислить.
   Для 1 <= i <= n пусть A (i) - длина самой длинной возрастающей последовательности ввода. Заметим, что длина, в которой мы в конечном счете заинтересованы, равна max{A(i)|1 ≤ i ≤ n} .
2. Дайте повторение.
   Для 1 <= i <= n A(i) = 1 + max{A(j)|1 ≤ j < i и input(j) < input(i)}.
3. Вычислить значения A.
4. Найти оптимальное решение.

Следующая программа использует A для вычисления оптимального решения. Первая часть вычисляет значение m такое, что A (m) - длина оптимальной возрастающей подпоследовательности ввода. Вторая часть вычисляет оптимальную возрастающую подпоследовательность, но для удобства мы ее распечатываем в обратном порядке. Эта программа выполняется во времени O (n), поэтому весь алгоритм работает во времени O (n ^ 2).

Часть 1:

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

Часть 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

Рекурсивное решение:

Подход 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

Сложность времени в подходе 1: O(n*2^n)

Подход 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], ∞)

Сложность времени в подходе 2: O(n^2)

Подход 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])

Сложность времени в подходе 3: O(n^2)

Итеративный алгоритм:

Вычисляет значения итеративно снизу вверх.

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

Сложность времени в итеративном подходе: O(n^2)

Вспомогательное пространство: O(n)

Позволяет принимать {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} в качестве входных данных. Таким образом, наибольшая возрастающая подпоследовательность для данного ввода - {0, 2, 6, 9, 11, 15} .

Реализация 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);
    }
}