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

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

Дано натуральное число n, затем последовательность из $n$ целых чисел. Из нее необходимо выбрать несколько подряд идущих чисел так, чтобы каждое следующее число было больше предыдущего. Какую максимальную сумму может иметь подпоследовательность из выбранных чисел?

Пример входных данных:

$|--| -1-- |2 | |--| |6-| -4-- |7 | |--| -9--$

Для указанных входных данных ответом должно быть число $20$ – максимальная сумма элементов возрастающей последовательности. В ответе укажите только целую часть числа.

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

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

f = open("27B.txt")
n = int(f.readline())
ans = 0
last = -1000000000
summa = 0

for i in range(n):
    cur = int(f.readline())
    if cur > last:
        summa += cur
        if summa > ans:
            ans = summa
    else:
        summa = cur
    last = cur

f.close()
print(ans)

Ответ: 22