Жауабы: Максимальная разность сумм
Два значения максимальной разности: для файла A и для файла B.
У этого задания официального ключа нет, поэтому ответ получен в разборе және кілтпен салыстырылмаған. Нәтижені жаттамас бұрын, өтіңіз выкладки — там видно, откуда взялось каждое число.
Бланкке: өлшем бірліктері жоқ сан немесе сөз; бөлшек бөлігін үтірмен бөліңіз.
Пусть $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.
Где здесь ошибаются
Разрешают соседние отрезки, забывая условие $R>M+1$.
Используют перебор всех троек $L$, $M$, $R$, что имеет кубическую или квадратичную сложность.
Путают знак разности и вычисляют сумму левого отрезка минус сумму правого.
Используют 32-битный тип данных без проверки диапазона сумм.