Блог

У нас есть специальный вариант задачи о самой длинной возрастающей подпоследовательности, где вместо одной пары векторов у нас есть две пары. Например:

 [0,1,2,3,4] <-> [3,0,1,2,4]
[3,4,0,2,1] <-> [0,4,3,2,1]
 

и решение [0,1,2].

Другими словами, пусть A-множество всех возрастающих подпоследовательностей из первой пары, а B-множество всех возрастающих подпоследовательностей из первой пары. Решением является размер наибольшего множества на пересечении A и B.

Обратите внимание, что мы преобразуем каждую возрастающую подпоследовательность в набор, поэтому при сравнении возрастающих подпоследовательностей из A и B нас не волнует порядок элементов в этих возрастающих подпоследовательностях.

вопрос:

Вопрос в том, существует ли алгоритм поли-времени, который решает этот вариант самой длинной возрастающей подпоследовательности?