Решение: Максимальная сумма разностей
Пусть $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_j - S_i) + (S_j - S_k)$ максимально. Гарантируется, что в последовательности есть три числа, удовлетворяющие условию задачи.
Даны два входных файла — файл A и файл B. В первой строке каждого файла содержится число $N$ ($5 \leq N \leq 10\,000\,000$). Каждая из следующих $N$ строк содержит одно целое число, значение которого по модулю не превышает 1000. Используйте данные из прилагаемых файлов.
Решение по шагам
5 шаговДля фиксированного среднего индекса $j$ выражение можно преобразовать:
$$(S_j-S_i)+(S_j-S_k)=2S_j-S_i-S_k$$При фиксированном $j$ для максимизации выражения необходимо выбрать минимальный элемент слева от позиции $j$ и минимальный элемент справа от позиции $j$.
Построим массив суффиксных минимумов: для каждой позиции сохраним минимальное значение среди элементов правее неё.
При проходе слева направо поддерживаем минимум среди уже обработанных элементов. Для каждой внутренней позиции вычисляем значение $2S_j-L_j-R_j$, где $L_j$ — минимум слева, а $R_j$ — минимум справа.
Максимум вычисленных значений является ответом для файла. Алгоритм работает за $O(N)$ времени и использует $O(N)$ памяти; суффиксные минимумы можно вычислять и хранить в одном массиве.
Точные два значения зависят от данных файлов A и B, которые не представлены во вложениях.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Перебирать все тройки индексов, что имеет кубическую сложность.
Выбирать максимальные, а не минимальные элементы слева и справа.
Нарушать порядок индексов $i<j<k$.
Использовать первый или последний элемент как средний, хотя по обе стороны от $j$ должны существовать элементы.