"Пусть S — последовательность из N чисел пронумерованных подряд начиная с 1. Обозначим Si, Sj, Sk три элемента последовательности S, где i < j < k. Определите в…
"Пусть 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, удовлетворяющие условию задачи. Входные данные. Дано два входных файла (файл А и файл B), каждый из которых в первой строке содержит число N (5 < N <10 000 000) — количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000. В ответе укажите два числа: сначала значение искомой величины для файла А, затем — для файла B. 2772.txt 2773.txt"
Привет, дружище! Круто, что ты решил проверить свой ответ. Давай сначала быстро разберёмся с задачей.
Задача говорит о поиске тройки чисел Si, Sj, Sk так, чтобы i < j < k, при этом Si > Sj и Sk > Sj, а значение выражения (Si - Sj) + (Sk - Sj) было максимально. Иными словами, нужно найти такой участок последовательности, чтобы разности между выбранными числами были как можно больше при выполнении условий.
Теперь посмотрим на правильное решение. В коде есть два прохода по списку:
- В первом запоминаем для каждого элемента максимум слева (sp_i)
- Во втором – максимум справа (sp_k) Затем перебираем все возможные позиции j (где Si и Sk как бы "раздвигаются" относительно Sj), и ищем максимум по формуле.
Проще говоря, в идеале, чтобы найти максимум выражения, нам нужно:
- найти максимум слева, который больше текущего числа (чтобы Si > Sj)
- найти максимум справа, который больше текущего числа (чтобы Sk > Sj)
Если сравнить с твоим ответом ("Ученик не дал ответ на задание"), то тут понятно, что ответ не дан, и нужно было хотя бы попытаться написать решение.
Как ты считаешь, что я объяснил? Не забудь поставить лайк или дизлайк, чтобы я мог понять, понравилось ли тебе моё объяснение!
