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