Наибольшая общая подпоследовательность

Найти наибольшую общую подпоследовательность двух списков. Максимальная длина списка 10³. Пример: наибольшая подпоследовательность последовательностей [0 5 3 9 3 3 8 4 2 5] и [9 0 7 6 5 0 3 7 1 0] является последовательность [0 5 3]. Реализовать алгоритм динамического программирования (смотрите Википедию или Хабр). Проверить правильность работы алгоритма прямым перебором.

Задание

В файле main.py нужно реализовать две функции:

• lcs_bf - находит наибольшую общую подпоследовательность полным перебором,
• lcs - делает то же самое, только используя динамическое программирование.

Обе функции:

• Принимают два целочисленных массива numpy - две исходные последовательности,
• Возвращают целочисленный массив numpy - найденная наибольшая общая подпоследовательность.

Функция lcs должна иметь сложность по времени и памяти не больше, чем O(N*M), где N и M - размеры входных массивов.

Тестирование

Запустить автоматические тесты можно так:

python -m pytest -sv -k lcs_bf # тестируем полный перебор
python -m pytest -sv -k lcs # тестируем динамическое программирование