Решение: Максимальная сумма разностей
Пусть $S$ — последовательность из $N$ целых чисел, пронумерованных подряд начиная с 1. Обозначим $S_i$, $S_j$, $S_k$ три элемента последовательности $S$, где $i < j < k$.
Определите в последовательности $S$ три таких числа $S_i$, $S_j$, $S_k$, что $S_i > S_j$, $S_k > S_j$, и значение выражения $(S_i - S_j) + (S_k - S_j)$ максимально. Гарантируется, что в последовательности есть три числа, удовлетворяющие условию задачи.
Дано два входных файла — файл A и файл B. Каждый из них в первой строке содержит число $N$ ($5 \leq N \leq 10\,000\,000$) — количество целых чисел. Каждая из следующих $N$ строк содержит одно целое число, значение которого по модулю не превышает 1000.
Для каждого файла найдите максимальное значение выражения $(S_i - S_j) + (S_k - S_j)$. При обработке файла B нельзя использовать переборный алгоритм, вычисляющий величину для всех возможных троек, поскольку такая программа будет выполняться слишком долго.
Решение по шагам
5 шаговПреобразуем выражение:
$$(S_i-S_j)+(S_k-S_j)=S_i+S_k-2S_j$$При фиксированном среднем индексе $j$ выгоднее всего выбрать максимальный элемент среди элементов с индексами меньше $j$ и максимальный элемент среди элементов с индексами больше $j$.
Для эффективной обработки можно заранее построить массив суффиксных максимумов: $R_j=\max(S_{j+1},\ldots,S_N)$. Затем пройти последовательность слева направо, поддерживая максимум $L_j=\max(S_1,\ldots,S_{j-1})$.
Для каждого допустимого $j$ вычисляем значение $L_j+R_j-2S_j$ и сохраняем наибольшее. Такой алгоритм работает за $O(N)$ времени.
Для файла B следует использовать потоковую обработку с двумя проходами или хранить только необходимые суффиксные максимумы, а не перебирать все тройки.
Численные ответы для файлов A и B нельзя определить без содержимого приложенных файлов.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Перебирать все тройки индексов, получая слишком большую сложность.
Использовать минимум вместо максимума слева или справа.
Забыть, что для среднего элемента $S_j$ должны существовать элементы и слева, и справа.
Вычислять $S_i+S_k-S_j$ вместо $S_i+S_k-2S_j$.