Изменения
Нет описания правки
# Подпалиндромом последовательности будем называть подпоследовательность $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$, в которой для любого $j$ выполняется $a_{i_j} = a_{i_{k-j+1}}$. Докажите, что длина максимального подпалиндрома последовательности $a$ равна длине наибольшей общей подпоследовательности $a$ и $a^r$, где $a^r$ {{---}} это развернутая последовательность $a$ ($a^r_i = a_{|a| - i + 1}$).
# Покажите, что если решить задачу о максимальном подпалиндроме, использовав алгоритм поиска наибольшей общей подпоследовательности, как в предыдущем задании, то алгоритм может выдать подпоследовательность, которая не является палиндромом. Предложите алгоритм, который находит максимальный подпалиндром последовательности $a$ за время и память $O(|a|^2)$.
# $a$ {{---}} последовательность длины $n$ из различных чисел от 1 до $n$. Докажите, что произведение длин наибольшей возрастающей и наибольшей убывающей подпоследовательностей в $a$ не меньше $n$.
# Заданы две последовательности $a$ и $b$. Числа в последовательности $a$ различны. Найдите наибольшую общую подпоследовательность $a$ и $b$ за время и память $O(|a| + |b|)$.
</wikitex>
