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

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

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

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

Для каждого файла найдите максимальное значение выражения $(S_i - S_j) + (S_k - S_j)$. При обработке файла B нельзя использовать переборный алгоритм, вычисляющий величину для всех возможных троек, поскольку такая программа будет выполняться слишком долго.

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

3169CC.zipАрхив ZIP · 1 МБВнутри: 319_27_B.txt, 319_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_j$?

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

$(S_i - S_j) + (S_k - S_j) = S_i + S_k - 2S_j$. Для каждого среднего элемента нужно знать максимальный элемент слева и максимальный элемент справа.

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

Последовательно поддерживайте максимум слева, а массив или суффиксные максимумы — справа. Для каждого $j$ вычисляйте $\mathrm{maxLeft} + \mathrm{maxRight} - 2S_j$ и обновляйте общий максимум.

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

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

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

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