Интересная задача с парой тонких моментов. Давайте читать условие:
Первое, на что стоит обратить внимание, это размер входных данных. Количество чисел до одного миллиона, и это обычно требует быстрого ввода (особенно на acmp), а удобные способы считывания данных не укладываются. Одним из способов быстрого считывания может быть считывание всей строки целиком одной операцией, а потом уже её разбор в коде и оперативной памяти. В C++ это можно реализовать с помощью stringstream, например. А в Python'е это стандартный способ ввода данных, поэтому давайте писать на нём:
Решать будем за один проход по массиву, поддерживая размер текущей пилообразной и размер максимальной. Тогда для очередного элемента надо будет проверить, продолжает ли он пилообразность и обновить наши значения. И тут мы встречаем второй тонкий момент - это одинаковые элементы, стоящие рядом. Например, если текущий элемент не продолжает текущую пилообразную последовательность, то возможны два варианта:
- 1 2 3 или 3 2 1 - текущий элемент продолжает возрастающее или нисходящее движение, тогда можно говорить он начале другой пилообразной последовательности длины 2: 2 3 или 2 1 соответственно;
- 1 2 2 - текущий элемент равен предыдущему, тогда только он является началом новой пилообразной последовательности длины 1.
Это необходимо учесть и при инициализации стартовых значений:
И при обработке каждого элемента:
Заметим, что благодаря множественным операциям сравнения в Python'е нет необходимости нагромождать сложное условие или делать его плохочитаемым с помощью арифметических операций:
Выбираем язык под задачу и получаем красивое решение.
Предыдущий выпуск: Задача 193. Поиск прямоугольников
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
