Задача А. Наибольшая чередующаяся подпоследовательность.
Задачу добавил: DK
Успешно сдано решений: 16
Эта задача настолько проста и известна, что в этот раз даже лень придумывать для нее условие.
Дано n целых чисел. Нужно найти наибольшую подпоследовательность, такую, что если Ai<Ai+1 то Ai+1>Ai+2, а если Ai>Ai+1 то Ai+1<Ai+2.
Входной файл.
В первой строке - натуральное число n <= 100000. В следующей строке n целых чисел через пробел - входная последовательность. Все числа входной последовательности по модулю не превосходят 10^7 и различны.
Выходной файл.
Единственное число - длина наибольшей чередующейся подпоследовательности.
Пример.
input.txt:
7
1 3 5 11 2 7 10
output.txt:
4
Подсказка: Например, искомой подпоследовательностью может являться "3 5 2 10"