|
Пусть
S
– последовательность из
N
целых чисел, пронумерованных подряд начиная с 1.
Обозначим
S
(
L
,
R
) подпоследовательность, состоящую из идущих подряд элементов, входящих в
S
, начиная
с элемента с номером
L
и заканчивая элементом с номером
R
включительно.
Требуется найти такую подпоследовательность
S
(
L
,
R
) максимальной длины, что сумма её элементов положительна
и чётна. Гарантируется, что хотя бы одна подпоследовательность требуемого вида существует.
В ответе укажите длину искомой подпоследовательности.
Входные данные
Дано два входных файла (файл
A
и файл
B
), каждый из которых
в первой строке содержит число
N
(5 ≤
N
≤ 10 000 000) – количество
целых чисел. Каждая из следующих
N
строк содержит одно целое число, значение которого по модулю не превышает 1000. В ответе
укажите два числа: сначала значение искомой величины для файла
А
, затем – для файла
B
.
Типовой пример организации данных во входном файле
6
–20
–3
8
–4
5
–10
При таких входных данных
L
= 2,
R
= 5. Сумма
подпоследовательности
равна ((–3) + 8 + (–4) + 5) = 6.
Ответом является длина этой подпоследовательности, равная 4.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.
Предупреждение:
для обработки файла
B
не следует
использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
|