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

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

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

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

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

A6A247.zipАрхив ZIP · 1,2 МБВнутри: 313_27_B.txt, 313_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_j – S_i) + (S_j – S_k) максимально. В ответе укажите найденное максимальное значение выражения (S_j – S_i) + (S_j – S_k). Гарантируется, что в последовательности есть три числа S_i, S_j, S_k, удовлетворяющие условию задачи.

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

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

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

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

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

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

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

Ваш ответ

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

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

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

Для каждого среднего элемента $S_j$ нужно независимо максимизировать левую разность $S_j-S_i$ при $i<j$ и правую разность $S_j-S_k$ при $k>j$.

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

Храните минимум среди уже просмотренных элементов слева и минимум среди элементов справа. Для фиксированного $S_j$ значение равно $2S_j - \min(S_i) - \min(S_k)$.

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

Сначала найдите минимум на суффиксе справа от каждой позиции, затем одним проходом слева направо вычисляйте $2S_j - \text{минимум слева} - \text{минимум справа}$ и запоминайте максимум.

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

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

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

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