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