Пусть S – последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три элемента последовательности S, где i < j < k. Определите в последовательности S три таких числа Si, Sj, Sk, что Si > Sj, Sk > Sj и значение выражения (Si – Sj) + (Sk – Sj) максимально. В ответе укажите найденное максимальное значение выражения (Si – Sj) + (Sk – Sj). Гарантируется, что в последовательности есть три числа Si, Sj, Sk, удовлетворяющие условию задачи. Входные данные Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (5 ≤ N ≤ 10 000 000) – количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000. В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B. Типовой пример организации данных во входном файле 9 6 9 7 5 8 6 10 –5 –6 При таких входных данных искомую максимальную сумму разностей образуют второй, четвёртый и седьмой элементы данной последовательности. Значение этой суммы разностей равно (9 – 5) + (10 – 5) = 9. Для седьмого, восьмого и девятого элементов последовательности искомая величина равна 14, но девятый элемент меньше восьмого, что не удовлетворяет условию задачи. Ответом является число 9. Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов. Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий искомую величину для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Для решения данной задачи необходимо найти три элемента \( S_i \), \( S_j \), \( S_k \) последовательности \( S \) таких, что: - \( S_i > S_j \) - \( S_k > S_j \) - \( i < j < k \) и при этом максимизировать величину \( (S_i - S_j) + (S_k - S_j) \). ### Шаг 1: Перепишем условие Упрощая выражение, мы можем записать его в виде: \[ (S_i - S_j) + (S_k - S_j) = S_i + S_k - 2S_j \] Таким образом, чтобы максимизировать выражение, нам надо: 1. Найти максимальное \( S_i \) для всех допустимых \( S_j \). 2. Найти максимальное \( S_k \) для всех допустимых \( S_j \). ### Шаг 2: Алгоритм решения 1. Создадим массив `max_left` длиной \( N \), где `max_left[j]` будет хранить максимальное значение \( S_i \) для каждого \( j \) (то есть для каждого \( S_j \)). Это можно сделать, проходя массив слева направо. 2. Создадим массив `max_right` длиной \( N \), где `max_right[j]` будет хранить максимальное значение \( S_k \) для каждого \( j \). Это можно сделать, проходя массив справа налево. 3. После заполнения этих двух массивов, пройдем по массиву \( S \) и будем вычислять значение \( (S_i - S_j) + (S_k - S_j) \) для каждого \( j \), используя соответствующие значения из `max_left` и `max_right`. ### Шаг 3: Реализация Теперь реализуем предложенный алгоритм. Обратите внимание, что мы должны пройти массив \( S \) три раза — один раз для `max_left`, один раз для `max_right`, и один раз для поиска максимального значения. ```python def find_max_expression(N, S): # Массив для хранения максимальных значений слева и справа max_left = [float('-inf')] * N max_right = [float('-inf')] * N # Заполнение max_left max_left[0] = S[0] for j in range(1, N): max_left[j] = max(max_left[j - 1], S[j]) # Заполнение max_right max_right[N - 1] = S[N - 1] for j in range(N - 2, -1, -1): max_right[j] = max(max_right[j + 1], S[j]) # Ищем максимальное значение выражения max_value = float('-inf') for j in range(1, N - 1): if S[j] < max_left[j] and S[j] < max_right[j]: # Убедимся, что есть допустимые S_i и S_k current_value = (max_left[j] - S[j]) + (max_right[j] - S[j]) max_value = max(max_value, current_value) return max_value # Пример использования: # Предположим, у нас есть числа из файла A и файла B: A = [6, 9, 7, 5, 8, 6, 10, -5, -6] B = [...] # Здесь вы должны загрузить остальные числа из файла B max_value_A = find_max_expression(len(A), A) max_value_B = find_max_expression(len(B), B) print(max_value_A, max_value_B) ``` ### Результат Функция `find_max_expression()` реализует описанный алгоритм и при подаче на неё массивов \( A \) и \( B \) будет выдавать запрашиваемые максимальные значения выражений для каждого из файлов. Этот подход работает за линейное время \( O(N) \), что позволяет обрабатывать большие массивы без переборного алгоритма.