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

Подается число N  , затем N  чисел, нужно найти максимальную сумму подряд идущих чисел, так что среди нет отрицательных.

Даны два входных файла (файл А и файл В), каждый из которых содержит в первой строке одно натуральное число N (1 ≤ N ≤ 1000000)  — количество чисел. Каждая из следующих N  строк содержит целое число. В ответе запишите максимальную сумму сначала для файла A, затем для файла B через пробел.

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

f = open("1.txt")
n = int(f.readline())
a = [int(f.readline()) for x in range(n)]
ans = 0
for i in range(n):
    sum = 0
    for j in range(i, n):
        if a[j] >= 0:
            sum += a[j]
        else:
            break
    ans = max(ans, sum)
print(ans)
f.close()

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

f = open("1.txt")
n = int(f.readline())
summa = 0
ans = 0
for i in range(n):
    x = int(f.readline())
    if x >= 0:
        summa += x
        ans = max(ans, summa)
    else:
        summa = 0
print(ans)
f.close()

Ответ: 42 9588
Оцените статью
Я решу все!