Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Задача А. Наибольшая чередующаяся подпоследовательность.

Задачу добавил: 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"

Сдать задачу

Задать вопрос жюри по этой задаче