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

Решение.

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

В первой строке файла записано K, во второй — N. Расстояние между позициями равно разности их номеров. Для i < j требуется j − i ≥ K, то есть i ≤ j − K. Равенство K допустимо.

Фиксируем позицию j. Среди допустимых элементов слева поддерживаем максимум на позициях до j − K включительно: перед проверкой j добавляем элемент aⱼ₋ₖ. При фиксированном aⱼ сумма монотонно возрастает по остальным слагаемым. Независимый выбор нужного экстремума с каждой стороны даёт максимум для данного j.

Перебираем j от K до N − 1 в нумерации программы от нуля. Все допустимые варианты представлены, а границы исключают повторное использование позиции. Начальное значение best = None не ограничивает возможный знак суммы. Целые числа Python точно хранят и большие произведения.

Важное уточнение к исходным данным: в условии указана верхняя граница 100000, однако исходный файл B содержит значения до 3571143; выше указанной границы находятся 3888300 записей. Ни одну запись не отбрасываем и не обрезаем. Требуемые максимальная сумма и расстояние между позициями определены для всех значений файла; приведённый алгоритм не зависит от этой ошибочной верхней границы.

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

from array import array

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

    left = a[0]
    best = None
    for j in range(k, n):
        left = max(left, a[j - k])
        value = left + a[j]
        if best is None or value > best:
            best = value
    return best

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

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

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

Файл A: (804) + (804) = 1608. Разности соседних выбранных номеров равны 401; каждая не меньше K = 20.

Файл B: (3571143) + (3571142) = 7142285. Разности соседних выбранных номеров равны 1496760; каждая не меньше K = 1000000.

Ответ: 1608 7142285.