Подпоследовательность длиной L
Задача
Дана последовательность из
N чисел. Рассматриваются все её непрерывные подпоследовательности, в которых количество отрицательных чисел
не превышает С. Найдите среди них подпоследовательность с максимальной суммой, длины
L. В ответе укажите сумму найденной подпоследовательности.
Входные данные
В первой строке записаны 3 числа: количество чисел
N (1 <= N <= 1 000 000),
L и
C (
\(1 <= L, C <= N <= 1 000 000\)). Каждая из следующих
N строк содержит одно число, не превышающее по модулю 1 000.
Пример организации исходных данных во входном файле (для L
= 3 и С = 3):
5 3 3
1
-1
2
-2
3
В этом наборе можно выбрать несколько последовательностей, но с максимальной суммой равной 3 будет: 2+(-2)+3.
Ответ (для
С = 3 и L = 3):
3.