Решение: Максимальная сумма осадков
По каналу связи передаётся последовательность целых неотрицательных чисел — показания прибора, полученные с интервалом в 1 мин в течение $T$ мин. Прибор измеряет количество атмосферных осадков, полученное регистратором за минуту, предшествующую моменту регистрации, и передаёт это значение в условных единицах измерения.
Определите два таких переданных числа, чтобы между моментами их передачи прошло не менее $K$ мин, а их сумма была максимально возможной. Укажите найденное суммарное количество осадков.
Даны два входных файла — файл А и файл B. Каждый файл в первой строке содержит натуральное число $K$ — количество минут, которое должно пройти между двумя передачами показаний, а во второй строке — количество переданных показаний $N$ ($1 \leq N \leq 10\,000\,000$, $N > K$). В каждой из следующих $N$ строк находится одно целое неотрицательное число, не превышающее $100\,000, обозначающее количество осадков за соответствующую минуту.
Для каждого файла найдите максимальную сумму двух элементов последовательности, номера которых отличаются не менее чем на $K$. Запишите сначала значение для файла А, затем значение для файла B.
Типовой пример: при $K=3$ и последовательности $15, 10, 200, 0, 30$ максимальная сумма равна $45$ — это сумма значений на первой и пятой минутах.
Для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных пар.
Решение по шагам
4 шагаПусть элементы последовательности имеют индексы от $0$ до $N-1$. Для элемента $a_i$ допустимы элементы $a_j$, для которых $i-j \geq K$, то есть $j \leq i-K$.
$$i-j \geq K$$При последовательном просмотре элементов поддерживаем максимум среди уже доступных элементов. Перед обработкой $a_i$ добавляем в этот максимум элемент $a_{i-K}$.
$$m_i = \max(m_{i-1}, a_{i-K})$$Сумма для текущего элемента равна сумме $a_i$ и накопленного максимума. Обновляем общий максимум.
$$S = \max(S, m_i + a_i)$$Алгоритм выполняется за $O(N)$ времени и использует $O(1)$ дополнительной памяти, если обрабатывать файл потоково с задержкой в $K$ элементов.
Ответы для файлов А и B определяются по приложенным входным файлам; сами файлы в предоставленных данных отсутствуют.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют только пары с расстоянием ровно $K$, хотя требуется расстояние не менее $K$.
Для каждого элемента перебирают все допустимые предыдущие элементы, получая сложность $O(N^2)$.
Неверно учитывают индексы и начинают использовать элемент раньше, чем между показаниями проходит $K$ минут.
Путают сумму максимальных элементов с максимальной суммой допустимой пары.