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

Решение.

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

Максимизируем сумму левого блока минус сумму правого. Положим vᵢ = aᵢ. Из L < M и M < R − 1 следует, что каждый блок содержит как минимум два элемента; блоки соседние.

Пусть P — префиксные суммы v и l = L − 1. Тогда разность равна (Pₘ − Pₗ) − (Pᵣ − Pₘ) = 2Pₘ − Pₗ − Pᵣ. При фиксированном M допустимы l ≤ M − 2 и R ≥ M + 2. Выбор левой и правой границы независим: берём минимальный Pₗ в левом диапазоне и минимальный Pᵣ в правом.

Заранее строим минимумы префиксных сумм справа. При движении M от 2 до N − 2 включительно обновляем минимум слева добавлением Pₘ₋₂ и вычисляем разность. Так проверены все допустимые середины и лучший выбор границ для каждой. Использование Pₘ₋₁ или Pₘ₊₁ допустило бы блок из одного элемента и решало бы другую задачу.

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

from array import array

def solve(name):
    sign = 1
    prefix = array("q", [0])
    with open(name, encoding="utf-8-sig") as f:
        n = int(f.readline())
        for _ in range(n):
            prefix.append(prefix[-1] + sign * int(f.readline()))
    right = array("q", prefix)
    for i in range(n - 1, -1, -1):
        right[i] = min(right[i], right[i + 1])
    left = prefix[0]
    best = None
    for mid in range(2, n - 1):
        left = min(left, prefix[mid - 2])
        value = 2 * prefix[mid] - left - right[mid + 2]
        if best is None or value > best:
            best = value
    return best

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

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

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

В обеих строках проверены L < M < R − 1. Разность сумм взята в порядке, заданном условием; обе суммы дополнительно рассчитаны непосредственно по выбранным отрезкам.

Ответ: 122522 150237357.