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