Задача к ЕГЭ по информатике на тему «Цепочки, выбор последовательности, префиксные суммы» №2

Просмотров 7 Комментарии 0

Дано число $n$ , затем последовательность из $n$ целых чисел. Рассматриваются все её непрерывные подпоследовательности. Найдите наибольшую сумму такой подпоследовательности.

Решение 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):
    cur = 0
    for j in range(i, n):
        cur += a[j]
        ans = max(ans, cur)
print(ans)

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

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

s = 0
mps = 0
ans = -10000000

for i in range(n):
    x = int(file.readline())
    s += x
    ans = max(ans, s - mps)
    mps = min(mps, s)
print(ans)

Ответ: 139294