Задача:

Даны два массива $$$A$$$, $$$B$$$ длин $$$N$$$. Требуется найти их наибольшую по длине общую подпоследовательность.

Решение:

Задача поиска наибольшей общей подпоследовательности двух массивов $$$A$$$ и $$$B$$$ длин $$$N$$$ и $$$N$$$ соответственно решается в общем случае за $$$O(N^2)$$$. Но задачу можно решить за $$$O(N log N)$$$, если в одном из массивов все элементы уникальны, без ограничения общности будем считать, что в массиве $$$А$$$.

Построим массив $$$C$$$ длины $$$N$$$ такой, что $$$C_i$$$ — индекс элемента $$$B_i$$$ в массиве $$$A$$$, или $$$-1$$$ если такого элемента нет в массиве $$$А$$$. Такой массив можно легко построить за $$$O(N log N)$$$, используя сортировки. Тогда очевидно что общей подпоследовательности $$$A$$$ и $$$B$$$ будет соответствовать некоторая возрастающая подпоследовательность массива C. Таким образом, найти ответ можно стандартным алгоритмом поиска наибольшей возрастающей подпоследовательности за $$$O(N log N)$$$, игнорируя при этом элементы равные $$$-1$$$.