Задание EGEINFA6A247: Эффективная обработка данных и кластеры

Решение.

Обрабатываем два приложенных текстовых файла отдельно. В файле A содержится 313 записей, в файле B — 999984. Заголовок задаёт параметры и не является элементом последовательности. Порядок исходных записей сохраняем. Числа из иллюстративного примера не заменяют данные файлов.

Пусть i < j < k — выбранные позиции. Средний элемент должен быть строго больше обоих крайних. Искомая величина равна (aⱼ − aᵢ) + (aⱼ − aₖ) = 2aⱼ − aᵢ − aₖ.

Положим vᵢ = aᵢ. В обоих случаях максимизируем 2vⱼ − vᵢ − vₖ. При фиксированном j левый и правый выбор независимы, поэтому выбираем минимум v слева и минимум v справа. Если один из этих минимумов не меньше vⱼ, подходящей тройки с данным средним элементом вообще нет.

Массив right[i] хранит минимум от позиции i до конца и строится справа налево. При просмотре j поддерживаем минимум строго левее j. Сравниваем оба минимума с vⱼ строгими неравенствами, затем обновляем общий максимум. Перебор всех внутренних j охватывает каждую допустимую тройку через её среднюю позицию; независимый выбор минимумов даёт лучший результат для этого j.

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

from array import array

def solve(name):
    with open(name, encoding="utf-8-sig") as f:
        n = int(f.readline())
        a = array("q", (int(f.readline()) for _ in range(n)))

    sign = 1
    v = array("q", (sign * x for x in a))
    right = array("q", v)
    for i in range(n - 2, -1, -1):
        right[i] = min(right[i], right[i + 1])
    left = v[0]
    best = None
    for j in range(1, n - 1):
        left = min(left, v[j - 1])
        if left < v[j] and right[j + 1] < v[j]:
            value = 2 * v[j] - left - right[j + 1]
            if best is None or value > best:
                best = value
    return best

print(solve('313_27_A.txt'), solve('313_27_B.txt'))

Время O(N), память O(N). Считывание и все арифметические действия выполняются над целыми числами; округление вычисленных ответов не требуется.

Проверка на исходных файлах. Номера элементов ниже отсчитываются от 1; полный алгоритм проверяет все допустимые варианты, а указанные позиции показывают достижение найденного результата.

Файл A: 2 · (297) − (-99) − (-95) = 788. Строгие сравнения среднего элемента с крайними выполнены.

Файл B: 2 · (321) − (-321) − (-321) = 1284. Строгие сравнения среднего элемента с крайними выполнены.

Ответ: 788 1284.