Я провел кучу исследований для поиска наиболее длинных для M = 2 последовательностей, но я пытаюсь выяснить, как это сделать для M >= 2 последовательностей. Мне даются последовательности N и M: M, с N уникальными элементами. N - множество {1 - N}. Я подумал о подходе к динамическому программированию, но я все еще путаюсь, как его включить.
Пример ввода 5 3 5 3 4 1 2 2 5 4 3 1 5 2 3 1 4
Максимальную последовательность здесь можно увидеть как 5 3 1
Ожидаемый результат
Длина = 3
Простая идея.
Для каждого номера i между 1 и N вычислите самую длинную подпоследовательность, где последнее число i. (Позвольте называть его a[i])
Для этого мы будем перебирать числа i в первой последовательности от начала до конца. Если a[i] > 1, то число j такое, что в каждой последовательности оно встречается до i.
Теперь мы можем просто проверить все возможные значения j и (если выполнено предыдущее условие) do a[i] = max(a[i], a[j] + 1).
Как последний бит, поскольку j предшествует i в первой последовательности, это означает, что a[j] уже рассчитан.
for each i in first_sequence
// for the OP example, 'i' would take values [5, 3, 4, 1, 2], in this order
a[i] = 1;
for each j in 1..N
if j is before i in each sequence
a[i] = max(a[i], a[j] + 1)
end
end
end
It O(N^2*M), если вы заранее рассчитали матрицу позиций.
Поскольку у вас есть уникальные элементы, ответ @Nikita Rybak - это тот, с которым нужно идти, но поскольку вы упомянули динамическое программирование, вот как вы будете использовать DP, если у вас есть более двух последовательностей:
dp[i, j, k] = length of longest common subsequence considering the prefixes
a[1..i], b[1..j], c[1..k].
dp[i, j, k] = 1 + dp[i - 1, j - 1, k - 1] if a[i] = b[j] = c[k]
= max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise
Чтобы получить истинную подпоследовательность назад, используйте рекурсивную функцию, начинающуюся с dp[a.Length, b.Length, c.Length], и в основном меняет приведенные выше формулы: если три элемента равны, вернитесь к dp[a.Length - 1, b.Length - 1, c.Length - 1] и напечатайте символ. Если нет, откат в соответствии с максимальным значением указанных выше значений.
Вы можете посмотреть в "" Дизайн нового детерминированного алгоритма поиска общей ДНК-подтекста". Вы можете использовать этот алгоритм для построения DAG (стр. 8, рис. 5). Из DAG читайте самые большие общие отдельные подпоследовательности. Затем попробуйте использовать метод динамического программирования, используя значение M, чтобы определить, сколько DAG необходимо построить для каждой последовательности. В основном используйте эти подпоследовательности в качестве ключа и сохраняйте соответствующие порядковые номера, где он найден, а затем попытайтесь найти самую большую подпоследовательность (которая может быть больше 1).