Решение: Максимальная разность сумм
Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S(L, R)$ подпоследовательность, состоящую из идущих подряд элементов, входящих в $S$, начиная с элемента с номером $L$ и заканчивая элементом с номером $R$. Требуется найти такие значения номеров элементов $L$, $M$, $R$, где $0 < L < M < R - 1$ (то есть между элементами с номерами $M$ и $R$ есть ещё как минимум один элемент), чтобы разность суммы элементов подпоследовательности $S(M+1, R)$ и суммы элементов подпоследовательности $S(L, M)$ была максимальна. В ответе укажите максимальное значение разности подобных сумм.
Даны два входных файла — файл A и файл B. В первой строке каждого файла содержится число $N$ ($5 \leq N \leq 10\,000\,000$) — количество целых чисел. Каждая из следующих $N$ строк содержит одно целое число, значение которого по модулю не превышает 1000. Для файла B нельзя использовать переборный алгоритм, вычисляющий разность для всех возможных вариантов.
В ответе укажите два числа: сначала значение искомой величины для файла A, затем — для файла B.
Решение по шагам
4 шагаОбозначим через $P_i$ сумму первых $i$ элементов последовательности, причём $P_0 = 0$. Тогда сумма элементов на отрезке $[L;M]$ равна $P_M-P_{L-1}$, а сумма элементов на отрезке $[M+1;R]$ равна $P_R-P_M$.
$$D=(P_R-P_M)-(P_M-P_{L-1})=P_R-2P_M+P_{L-1}$$Для каждого правого конца $R$ необходимо найти минимум величины $2P_M-P_{L-1}$ среди всех допустимых пар $L<M<R-1$. При увеличении $R$ в множество допустимых пар добавляется новая пара с $M=R-2$ и всеми допустимыми $L<M$.
$$D_R=P_R-\min(2P_M-P_{L-1})$$Минимум можно поддерживать одной переменной. После обработки каждого элемента вычисляется очередное значение $P_R$, обновляется ответ и добавляется в минимум подходящая пара. Алгоритм выполняется за $O(N)$ времени и использует $O(N)$ памяти при хранении префиксных сумм либо $O(1)$ дополнительной памяти при потоковой обработке с необходимыми задержанными значениями.
Полученный алгоритм применяют отдельно к файлу A и к файлу B. Числовые ответы зависят от содержимого приложенных файлов.
Два значения максимальной разности: для файла A и для файла B.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Разрешают соседние отрезки, забывая условие $R>M+1$.
Используют перебор всех троек $L$, $M$, $R$, что имеет кубическую или квадратичную сложность.
Путают знак разности и вычисляют сумму левого отрезка минус сумму правого.
Используют 32-битный тип данных без проверки диапазона сумм.