Дана последовательность натуральных чисел. Необходимо найти максимально возможную сумму её непрерывной подпоследовательности, в которой количество чётных элементов кратно 
.
Входные данные
Первая строка входного файла содержит целое число 
— общее количество чисел в наборе. Каждая из следующих 
строк содержит одно число. Гарантируется, что общая сумма всех чисел не превышает 
.
Вам даны два входных файла (
и 
), каждый из которых имеет описанную выше структуру. В ответе укажите два числа: сначала значение искомой суммы для файла 
, затем для файла 
.
Решение 1 (неэффективное)
f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 0
for i in range(n):
cnt, sum = 0, 0
for j in range(i, n):
sum += a[j]
if a[j] % 2 == 0:
cnt += 1
if cnt % 10 == 0:
ans = max(ans, sum)
print(ans)
Решение 2 (эффективное)
f = open(’Задание_27-B__aht7__tmxb.txt’)
n = int(f.readline())
mx = 0 # максимальная сумма подпоследовательности
s = 0 # сумма всех чисел файла
count = 0 # количество чётных чисел всего файла
K = 10 # чему должно быть кратно количество чётных чисел
tails = [10**30]*K # список, в котором под каждым индексом будут записаны минимальные префиксные суммы.
# определенный индекс обозначает остаток при делении на 3.
# Например, tails[2] - это префиксная сумма, у которой количество чётных чисел даёт остаток 2 при делении на 10
for i in range(n):
x = int(f.readline()) # считываем текущее число
s += x
if x % 2 == 0: # если текущее число - чётное
count += 1 # увеличиваем счётчик
if count % K == 0: # если счётчик кратен 10
mx = max(mx,s) # перезаписываем максимум
# если в сумме s количество чётных чисел не кратно 10
# тогда убавляем такую префиксную сумму,
# после которой в полученной подпоследовательности количество чётнных чисел будет кратно 10
s1 = s - tails[count % K]
mx = max(mx,s1) # перезаписываем максимум
# перезаписываем префиксные суммы под определенным остатком при делении на 10
tails[count % K] = min(tails[count % K], s)
print(mx)