Пусть S — последовательность из N чисел пронумерованных подряд начиная
Условие
Пусть 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Дано два входных файла (файл А и файл B), каждый из которых в первой строке содержит число N (5 < N <10 000 000) — количество целых чисел. Каждая из следующих N строк содержит одно целое число, значение которого по модулю не превышает 1000. В ответе укажите два числа: сначала значение искомой величины для файла А, затем — для файла B. Ответ:
Ответ
Ответ и полный разбор откроются после входа
Посмотреть ответРешение по шагам
Как рассуждать
Решение. Приведём решение на языке Python.f = open('2772.txt')n = int(f.readline())a = [int(x) for x in f]sp_i = [-1010]*ncurMx = -1010for i in range(n): curMx = max(curMx, a[i]) sp_i[i] = curMxsp_k = [-10**10]*ncurMx = -10 ** 10for k in range(n-1, -1, -1): curMx = max(curMx, a[k]) sp_k[k] = curMxres = 0for j in range(1, n-1): if a[j] < sp_i[j-1] and a[j] < sp_k[j+1]: res = max(res, (sp_i[j-1] - a[j]) + (sp_k[j+1] - a[j]))print(res)
Осталось ещё 2 шага
Приведём решение Юрия Красильникова на языке…
if left[i-1] > a[i] and right[i+1] >…
Бесплатно · займёт минуту