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

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

def is_prime(n):
    if n < 2:
        return False
    for j in range(2, int(n ** 0.5) + 1):
        if n % j == 0:
            return False
    return True


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 = 0
    sum = 0
    for j in range(i, n):
        sum += a[j]
        if is_prime(a[j]):
            cnt += 1
        if cnt % 3 == 0:
            ans = max(ans, sum)
print(ans)

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

def is_prime(n): # функция для проверки числа на простоту
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


f = open(’Задание_27_B__qjvf__t6o1.txt’)
n = int(f.readline())


mx = 0 # максимальная сумма подпоследовательности
s = 0 # сумма всех чисел файла
count = 0 # количество простых чисел всего файла
K = 3 # чему должно быть кратно количество простых чисел
tails = [10**30]*K # список, в котором под каждым индексом будут записаны минимальные префиксные суммы.
# определенный индекс обозначает остаток при делении на 3.
# Например, tails[2] - это префиксная сумма, у которой количество просто чисел даёт остаток 2 при делении на 3
for i in range(n):
    x = int(f.readline()) # считываем текущее число
    s += x
    if is_prime(x): # если текущее число - простое
        count += 1 # увеличиваем счётчик
    if count % K == 0: # если счётчик кратен 3
        mx = max(mx,s) # перезаписываем максимум
    # если в сумме s количество простых чисел не кратно 3
    # тогда убавляем такую префиксную сумму,
    # после которой в полученной подпоследовательности количество простых чисел будет кратно 3
    s1 = s - tails[count % K]
    mx = max(mx,s1) # перезаписываем максимум
    # перезаписываем префиксные суммы под определенным остатком при делении на 3
    tails[count % K] = min(tails[count % K], s)
print(mx)