algorithm
Самая продолжительная подпоследовательность
Поиск…
Самая длинная нарастающая базовая информация
Задача « Самая длинная нарастающая подпоследовательность» заключается в том, чтобы найти подпоследовательность из входной последовательности give, в которой элементы подпоследовательности отсортированы в младшем и высоком порядке. Все подпоследовательности не являются непрерывными или уникальными.
Применение наиболее долговременной последовательности:
Алгоритмы, такие как Longest Increasing Subsequence, Longest Common Subsequence, используются в системах контроля версий, таких как Git и т. Д.
Простая форма алгоритма:
- Найдите уникальные строки, общие для обоих документов.
- Возьмите все такие строки из первого документа и закажите их в соответствии со своим внешним видом во втором документе.
- Вычислите LIS результирующей последовательности (сделав терпение Сортировка ), получив самую длинную совпадающую последовательность строк, соответствие между строками двух документов.
- Учтите алгоритм для каждого диапазона строк между уже согласованными.
Теперь рассмотрим более простой пример проблемы LCS. Здесь ввод представляет собой только одну последовательность различных целых чисел a1,a2,...,an.
, и мы хотим найти в нем самую длинную возрастающую подпоследовательность. Например, если вход 7,3,8,4,2,6, то самая длинная возрастающая подпоследовательность составляет 3,4,6 .
Самый простой способ - сортировать входные элементы в порядке возрастания и применять алгоритм LCS к исходным и отсортированным последовательностям. Однако, если вы посмотрите на результирующий массив, вы заметите, что многие значения одинаковы, и массив выглядит очень повторяющимся. Это говорит о том, что проблема LIS (самая длинная возрастающая подпоследовательность) может быть выполнена с помощью алгоритма динамического программирования, использующего только одномерный массив.
Псевдокод:
- Опишите массив значений, которые мы хотим вычислить.
Для1 <= i <= n
пусть A (i) - длина самой длинной возрастающей последовательности ввода. Заметим, что длина, в которой мы в конечном счете заинтересованы, равнаmax{A(i)|1 ≤ i ≤ n}
. - Дайте повторение.
Для1 <= i <= n
A(i) = 1 + max{A(j)|1 ≤ j < i
иinput(j) < input(i)}.
- Вычислить значения A.
- Найти оптимальное решение.
Следующая программа использует 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);
}
}