Пусть S – последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три элемента последовательности S, где i < j < k. Определите в…

Для решения данной задачи необходимо найти три элемента \( 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, и один раз для поиска максимального значения.

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) \), что позволяет обрабатывать большие массивы без переборного алгоритма.