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