Олимпиадная информатика

события, задачи, тесты, решения, комментарии

МИОО, МЦНМО, Оргкомитет Московской олимпиады по информатике

Дистанционные семинары
по подготовке к олимпиадам по информатике

Задача 02-3. "Подпоследовательности"
(Разбор)

Пусть c₁,c₂, ... ,c_n, - данная последовательность. Покажем, как найти длину максимальной возрастающей подпоследовательности, заканчивающуюся в элементе c_k (обозначим a_k). Предположим, она уже найдена. Удалим из нее последний элемент. Полученная подпоследовательность является максимальной возрастающей подпоследовательностью, оканчивающейся в некотором элементе c_j (j < k). Значит, либо a_k = max_{{j < k, cj < ck}}{a_j} + 1, либо a_k = 1, если таких j не существует. Ответом на поставленную задачу будет максимум из всех a_k.

Число действий, выполненных данным алгоритмом, пропорционально N².