Наибольшая пилообразная подпоследовательность
Числовая последовательность называется пилообразной если каждый ее член (кроме первого и последнего) либо больше обоих своих соседей, либо меньше обоих соседей. Например, последовательность 1, 2, 1, 3, 2 является пилообразной, а 1, 2, 3, 1, 2 — нет, поскольку 1 < 2 < 3. Любая последовательность из одного элемента является пилообразной. Последовательность из двух элементов является пилообразной, если ее элементы не равны.
Дана последовательность. Требуется определить, какое наименьшее количество ее членов нужно вычеркнуть, чтобы оставшаяся последовательность оказалась пилообразной.
Формат входных данных
В первой строке входного файла записано одно число N (1≤N≤100000) — количество членов последовательности. Во второй строке записано N натуральных чисел, не превосходящих 10 000 — члены последовательности.
Формат выходных данных
В выходной файл выведите одно число — минимальное количество членов, которые необходимо вычеркнуть.
Дана последовательность. Требуется определить, какое наименьшее количество ее членов нужно вычеркнуть, чтобы оставшаяся последовательность оказалась пилообразной.
Формат входных данных
В первой строке входного файла записано одно число N (1≤N≤100000) — количество членов последовательности. Во второй строке записано N натуральных чисел, не превосходящих 10 000 — члены последовательности.
Формат выходных данных
В выходной файл выведите одно число — минимальное количество членов, которые необходимо вычеркнуть.
Изменим нашу задачу на задачу о нахождении длины наибольшей пилообразной подпоследовательности, которую можно получить из данной последовательности.
Рассмотрим пилообразную последовательность длины l. Она состоит из возрастающих и убывающих подпоследовательностей, суммарное количество которых равно l-1.
Теперь посмотрим на заданную последовательность. Возможны два варианты:
1) Заданная последовательность состоит из одинаковых элементов. Тогда ответ очевиден.
2) В заданной последовательности есть хотя бы одна возрастающая или убывающая подпоследовательность. Удалим из неё все подрядыдущие одинаковые элементы (понятно, что это нужно сделать, чтобы последовательность стала пилообразной). Получившаяся последовательность состоит из последовательно записанных возрастающих и убывающих подпоследовательностей, в которых соседние пересекаются по одному элементу. К примеру, последовательность 1 2 3 4 3 1 5 состоит из двух возрастающих (1 2 3 4 и 1 5) и одной убывающей (4 3 1). Понятно, что ответом будем количество таких подпоследовательностей (обозначим его за k), увеличенное на единицу. Почему ответ не может быть больше? Предположим, что это так. Но тогда существует как минимум k+1 возрастающих и убывающих подпоследовательностей, а в заданной последовательности их всего k. Значит, предположение неверно.
Рассмотрим пилообразную последовательность длины l. Она состоит из возрастающих и убывающих подпоследовательностей, суммарное количество которых равно l-1.
Теперь посмотрим на заданную последовательность. Возможны два варианты:
1) Заданная последовательность состоит из одинаковых элементов. Тогда ответ очевиден.
2) В заданной последовательности есть хотя бы одна возрастающая или убывающая подпоследовательность. Удалим из неё все подрядыдущие одинаковые элементы (понятно, что это нужно сделать, чтобы последовательность стала пилообразной). Получившаяся последовательность состоит из последовательно записанных возрастающих и убывающих подпоследовательностей, в которых соседние пересекаются по одному элементу. К примеру, последовательность 1 2 3 4 3 1 5 состоит из двух возрастающих (1 2 3 4 и 1 5) и одной убывающей (4 3 1). Понятно, что ответом будем количество таких подпоследовательностей (обозначим его за k), увеличенное на единицу. Почему ответ не может быть больше? Предположим, что это так. Но тогда существует как минимум k+1 возрастающих и убывающих подпоследовательностей, а в заданной последовательности их всего k. Значит, предположение неверно.
