Максимальная разность сумм
Пусть $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 нельзя использовать переборный алгоритм, вычисляющий разность для всех возможных вариантов.
Условие как в банке ФИПИ — открыть и сверить
| ||||||
| | ||||||
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Выразите суммы двух частей через префиксные суммы и разделите перебор по позиции $M$.
2Наводящая — какие числа считатьуровень 2 из 3
Для фиксированного $M$ нужно максимизировать сумму $S(L, M)$ по $L < M$ и минимизировать сумму $S(M + 1, R)$ по $R \geq M + 2$.
3Прямая — фактически решениеуровень 3 из 3
Одним проходом слева направо поддерживайте максимум суммы от допустимого начала до текущей позиции, а справа налево заранее вычислите минимальные суммы от позиции до конца. Для каждого $M$ объедините левый максимум и правый минимум.