.04 Пары/тройки чисел, выбрать из каждой, кратность

Переборное решение

Будем перебирать три числа в тройном цикле на расстоянии K друг от друга и обновлять максимальную сумму.

# Открываем файл
file = open("27_A_2024.txt")

# Считываем K и N
k = int(file.readline())
n = int(file.readline())

# Считываем показания прибора
data = list(map(int, file))

# Задаём максимальную сумму очень маленьким числом
max_sum = -(10**100)

# Перебираем первое, второе и третье число на расстоянии k друг от друга
for i1 in range(n):
    for i2 in range(i1 + k, n):
        for i3 in range(i2 + k, n):
            # Обновляем максимальную сумму
            max_sum = max(max_sum, data[i1] + data[i2] + data[i3])

# Выводим ответ
print(max_sum)

Динамическое решение

Для начала посмотрим на немного упрощённую задачу: будем искать пару чисел с максимальной суммой. Числа у нас будут лежать в списке .

Первая возможная пара чисел — это и . К надо взять , к — и так далее. То есть для любого индекса , , следует брать .

Теперь добавим третье число. К нему мы хотим добавлять пару с максимальной суммой на подходящем расстоянии. При переборе третьего числа по , , мы хотим к нему брать два числа с максимальной суммой из с достаточным расстоянием между собой. И мы ведь уже научились находить пару чисел с максимальной суммой на правильном расстоянии.

# Открываем файл
file = open("27_B_2024.txt")

# Считываем K и N
k = int(file.readline())
n = int(file.readline())

# Считываем показания прибора
data = list(map(int, file))

# Максимальное число в data[0 : i - k * 2 + 1]
one = 0
# Максимальная сумма пары среди data[0 : i - k + 1]
two_sum = 0
# Максимальная сумма тройки
three_sum = 0

# Перебираем с минимального индекса, с которого можно взять тройку
for i in range(k * 2, n):
    # Обновляем максимальное число за k * 2 до текущего
    one = max(one, data[i - k * 2])
    # Обновляем максимальную сумму пары за k до текущего
    two_sum = max(two_sum, one + data[i - k])
    # Обновляем максимальную сумму тройки
    three_sum = max(three_sum, two_sum + data[i])

# Выводим ответ
print(three_sum)