Решение: Максимальная сумма трёх показаний
По каналу связи передаётся последовательность целых чисел — показания прибора. В течение $N$ минут прибор ежеминутно регистрирует значение напряжения в электрической сети и передаёт его на сервер. Определите три таких переданных числа, чтобы между моментами передачи любых двух из них прошло не менее $K$ минут, а сумма этих трёх чисел была максимально возможной. Даны два входных файла — файл А и файл B. В первой строке каждого файла записано натуральное число $K$, во второй — количество переданных показаний $N$ ($1 \leq N \leq 10\,000\,000$, $N > K$). В следующих $N$ строках записаны целые числа, по модулю не превышающие $10\,000\,000$. Для файла А допускается переборный алгоритм, но для файла B необходимо использовать алгоритм, работающий достаточно быстро на $N$ до $10\,000\,000$. Типовой пример: при $K=2$ и последовательности $150, -150, 20, -200, -300, 0$ искомая сумма равна $170$.
Решение по шагам
5 шаговНумеруем показания от $0$ до $N-1$. Для текущего показания $a_i$ предыдущие выбранные показания должны иметь индексы не больше $i-K$.
Поддерживаем три величины: максимальное значение одного допустимого показания, максимальную сумму пары, второй элемент которой уже допустим для текущего положения, и максимальную найденную сумму трёх показаний.
При переходе к позиции $i$ добавляем в множество допустимых одиночных элементов значение $a_{i-K}$. Пара, заканчивающаяся в позиции $i$, имеет сумму $a_i$ плюс максимум одиночного элемента, допустимого для этой позиции.
Перед обработкой $a_i$ в максимум пар добавляем значение пары, заканчивающейся в позиции $i-K$. Тогда текущая тройка может состоять из этой лучшей пары и $a_i$.
Каждая позиция обрабатывается один раз, поэтому время работы алгоритма равно $O(N)$, а дополнительная память — $O(1)$.
Численные ответы зависят от содержимого приложенных файлов А и B; без этих файлов определить два числа невозможно.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют только соседние позиции и забывают о расстоянии между любыми двумя выбранными показаниями.
Используют перебор всех троек, имеющий слишком большую сложность.
Добавляют элемент в структуру допустимых значений раньше, чем разрешено условием расстояния $K$.
Не учитывают отрицательные значения показаний.