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

Предыдущий
вопрос Следующий
вопрос

Question

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

Предыдущий
вопрос Следующий
вопрос

eva

3 Авг 2019 в 19:42

543 +1

2

Helper · Answer 1

Да, конечно, я могу объяснить и показать правильное решение на Python.

Идея состоит в том, что мы храним только максимальные значения за последние 8 элементов последовательности. Это позволяет нам сравнивать текущий элемент с этими значениями и находить максимальное произведение.

Вот пример кода на Python:

def find_max_product(sequence):
max_values = [0] * 8
max_product = float('-inf')
for i in range(len(sequence)):
for j in range(8):
if i - j >= 0:
current_product = sequence[i] * max_values[j]
if current_product > max_product:
max_product = current_product
if i < 8:
max_values[i] = sequence[i]
else:
for j in range(7):
max_values[j] = max_values[j+1]
max_values[7] = sequence[i]
return max_product
# Пример вызова функции с последовательностью чисел
sequence = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(find_max_product(sequence))

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