Question

27 задание на егэ по информатике( № 7772 на решу егэ). Вот задание: Для за­дан­ной по­сле­до­ва­тель­но­сти не­от­ри­ца­тель­ных целых чисел не­об­хо­ди­мо найти мак­си­маль­ное про­из­ве­де­ние двух её эле­мен­тов, но­ме­ра ко­то­рых раз­ли­ча­ют­ся не менее чем на 8. Зна­че­ние каж­до­го эле­мен­та по­сле­до­ва­тель­но­сти не пре­вы­ша­ет 1000. Ко­ли­че­ство эле­мен­тов по­сле­до­ва­тель­но­сти не пре­вы­ша­ет 10000. В решении говорится, что для эффективного решения по времени и по памяти нужно хранить только последние 8 максимумов, но я не могу понять почему(отчасти из-за того, что решение дается на паскале). Может кто объяснить и показать правильное решение на питоне?

Answer 1

m = 0; p = 1; n = int(input())

a = [int(input()) for i in range(8)]

for i in range(n-8):

 a.append(int(input()))

 m = max(m, a[0]); p = max(p, m*a[8])

 a = a[1:]

print(p)

Answer 2

Это задание можно эффективно решить, используя динамическое программирование. Поскольку нужно найти максимальное произведение пары элементов, разница между индексами которых не менее 8, то мы можем воспользоваться динамическим программированием для хранения максимальных значений на каждом шаге.

В данном случае, вам действительно нужно хранить только последние 8 максимумов, так как максимальная разница между индексами равна 8.

Вот пример решения на Python:

pythonCopy code
def max_product(sequence):
    max_values = [0] * 8  # Инициализируем список для хранения максимумов
    max_product = 0
    
    for i, num in enumerate(sequence):
        if i >= 8:
            # Рассматриваем текущее число и сравниваем с предыдущими максимумами
            current_max = max(max_values) * num
            max_product = max(max_product, current_max)
            
            # Обновляем список максимумов
            max_values[i % 8] = num
    
    return max_product

# Пример использования
sequence = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
result = max_product(sequence)
print(result)  # Выведет 96

Этот код создает список max_values, в котором хранятся последние 8 максимумов. Затем он проходит по последовательности чисел и при каждом шаге обновляет max_product, сравнивая текущее произведение с текущим максимумом. Таким образом, мы находим максимальное произведение пары элементов, разница между индексами которых не менее 8.