Пусть 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.
Ответ:
Решение. Приведём решение на языке Python.
f = open('2772.txt')
n = int(f.readline())
a = [int(x) for x in f]
sp_i = [-10**10]*n
curMx = -10**10
for i in range(n):
curMx = max(curMx, a[i])
sp_i[i] = curMx
sp_k = [-10**10]*n
curMx = -10 ** 10
for k in range(n-1, -1, -1):
curMx = max(curMx, a[k])
sp_k[k] = curMx
res = 0
for 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)
Ответ: 4000 3996.
Приведём решение Юрия Красильникова на языке Python.
a = [int(s) for s in open('27.txt')][1:]
left = [a[0]]
for x in a[1:]: left.append(max(left[-1],x))
right = [a[-1]]
for x in a[-2::-1]: right.append(max(right[-1],x))
right = right[::-1]
r = [left[i-1] + right[i+1] - 2*a[i] for i in range(1,len(a) - 1) if left[i-1] > a[i] and right[i+1] > a[i]]
PDF-версии: горизонтальная · вертикальная · крупный шрифт · с большим полем