Максимальная сумма разностей

ЕГЭ · Информатика · Задание 27 · Динамическое программирование

ВысокаяФИПИ38414EКороткий ответ≈ 15 минут

Пусть $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 необходимо использовать алгоритм, не перебирающий все возможные тройки элементов.

Файл к заданию

38414E.zipАрхив ZIP · 1 МБВнутри: 325_27_B.txt, 325_27_A.txt

Условие как в банке ФИПИ — открыть и сверить

Впишите правильный ответ.

Задание выполняется с использованием прилагаемых
файлов.

Пусть 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) максимально. В ответе укажите найденное максимальное значение выражения (S_i – S_j) + (S_k – S_j). Гарантируется, что в последовательности есть три числа S_i, S_j, S_k, удовлетворяющие условию задачи.

Входные данные

Дано два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N (5 ≤ N ≤ 10 000 000) – количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем – для файла B.

Типовой пример организации данных во входном файле

–5

–6

При таких входных данных искомую максимальную сумму разностей образуют второй, четвёртый и седьмой элементы данной последовательности. Значение этой суммы разностей равно (9 – 5) + (10 – 5) = 9. Для седьмого, восьмого и девятого элементов последовательности искомая величина равна 14, но девятый элемент меньше восьмого, что не удовлетворяет условию задачи. Ответом является число 9.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий искомую величину для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.

Ваш ответ

Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.

3 уровня: от лёгкого толчка до почти готового решения. Следующий открывается, когда прочитан предыдущий, — чтобы не перепрыгнуть сразу к ответу.

1Мягкая — с чего смотретьуровень 1 из 3

Как можно представить выражение $(S_i-S_j)+(S_k-S_j)$ через сумму двух величин, зависящих от разных частей последовательности?

2Наводящая — какие числа считатьуровень 2 из 3

Для каждого среднего элемента $S_j$ нужно знать максимальный элемент слева и максимальный элемент справа: значение равно $\max_{i<j} S_i + \max_{k>j} S_k - 2S_j$.

3Прямая — фактически решениеуровень 3 из 3

Просматривайте последовательность слева направо, поддерживая максимум слева, а максимумы справа заранее вычислите суффиксным проходом. Для каждого $j$ обновляйте общий максимум.

Всё равно не складывается?Полное решение с обоснованием каждого шага — на отдельной странице.

Открыть решение

ПредыдущаяМаксимальная сумма разностейСледующаяМаксимальная разность сумм

Задание 27 ЕГЭ, информатика