Решение: Максимальная сумма осадков
По каналу связи передаётся последовательность целых неотрицательных чисел — показания прибора, полученные с интервалом в 1 мин в течение $T$ минут. Определите два переданных числа, чтобы между моментами их передачи прошло не менее $K$ минут, а их сумма была максимально возможной. Даны два входных файла: файл A и файл B. В первой строке каждого файла записано натуральное число $K$, во второй — количество переданных показаний $N$ ($1 \leq N \leq 10\,000\,000$, $N > K$). В следующих $N$ строках записаны значения осадков за соответствующие минуты. Запишите сначала искомую величину для файла A, затем для файла B. Для файла B необходимо использовать алгоритм, не перебирающий все пары показаний.
Решение по шагам
4 шагаЕсли два показания имеют индексы $j$ и $i$, то условие задачи имеет вид $i-j \geq K$. При фиксированном $i$ выгодно выбрать среди допустимых предыдущих элементов максимальный.
$$j \leq i-K$$При последовательном чтении данных поддерживаем максимум всех элементов с индексами от $0$ до $i-K$. После обработки очередного элемента обновляем этот максимум и рассматриваем сумму с текущим значением.
$$S_i=a_i+\max_{0\leq j\leq i-K}a_j$$Максимум среди доступных элементов можно поддерживать за $O(1)$ для каждого показания, поэтому общая временная сложность алгоритма составляет $O(N)$, а дополнительная память — $O(1)$ при потоковой обработке.
По данным файлов A и B вычисляются два максимальных значения. Числа файлов в предоставленных данных в условии не приведены, поэтому конкретные значения ответов определить невозможно.
Ответы для файлов A и B получают однопроходным алгоритмом по формуле $\max_{i\geq K}\left(a_i+\max_{j\leq i-K}a_j\right)$.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют только элементы с разностью индексов ровно $K$, хотя требуется расстояние не менее $K$.
Перебирают все пары элементов, получая сложность $O(N^2)$.
Добавляют в максимум элемент с индексом $i-K+1$, нарушая условие минимального расстояния.
Путают номер показания и количество минут между моментами его передачи.