Какой алгоритм наиболее оптимален для поиска ВСЕХ наиболее длинных увеличивающихся подпоследовательностей?
Я пытаюсь найти ВСЕ длинную возрастающую подпоследовательность массива. Я мог бы найти одну такую ЛИС в O(n log n) используя бинарный поиск, как предложено в Википедии.
Может ли кто-нибудь помочь мне, как я могу продлить то же самое для поиска всех таких LIS. Я не могу найти лучший способ сделать это более чем O(n²), Любое предложение по оптимизации было бы очень полезно.
2 ответа
Рассмотрим этот список:
2,1, 4,3, 6,5, 8,7, 10,9, ..., 2m,2m-1
Самая длинная увеличивающаяся длина последовательности этого списка m = n/2, Вы можете легко построить такую последовательность, выбрав один элемент из каждой "пары" элементов. Так как есть m такие пары, и выбор независимы, есть 2^m самые длинные увеличивающиеся последовательности.
Таким образом, ваш алгоритм не может быть быстрее, чем Ω(2^(n/2)) потому что в некоторых случаях по крайней мере так много выходных.
Чтобы обойти это, вам нужно откорректировать проблему, возможно, выполнив чувствительный к выходу анализ или посчитав количество последовательностей вместо того, чтобы фактически генерировать их. Другой альтернативой является вывод компактного способа, который можно использовать позже для генерации всех последовательностей, что и делают алгоритмы линейного объединения времени.
Таких последовательностей может быть экспоненциально много. Вы, конечно, не можете перечислить их в квадратичном времени.
За время O(n log(n)) вы можете найти длину самых длинных увеличивающихся подпоследовательностей, начинающихся и заканчивающихся в каждой позиции в массиве. Затем вы можете перечислить все самые длинные растущие подпоследовательности с помощью простой рекурсии.