27.03 Цепочки, выбор последовательности, префиксные суммы

Решение 1 (неэффективное)

f = open("27A.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = -1000000000
for i in range(n):
    cnt = 0
    sum = 0
    for j in range(i, n):
        sum += a[j]
        if a[j] < 0:
            cnt += 1
        if cnt % 10 == 0:
            ans = max(ans, sum)
print(ans)

Решение 2 (эффективное)

file = open(’27B.txt’, ’rt’)
n = int(file.readline())

s = 0
k = 0
mps = [0] + [10000000 for _ in range(9)]
ans = -1000000

for i in range(n):
    x = int(file.readline())
    s += x
    if x < 0:
        k += 1
    ans = max(ans, s - mps[k % 10])
    mps[k % 10] = min(mps[k % 10], s)
print(ans)