Как обойти ошибку «Превышен лимит памяти»?

Question

[Andraaaaaa]

Мой код на Python не проходит лимит памяти в 64Мб

Моя задача: Я пытаюсь найти из списка сторон такие, чтобы получаемый меж ними прямоугольник был максимальной площади Функционально все работает, а вот ограничение памяти не проходит

length = input().split()
data = [int(x) for x in length]
data_copy = data


n = len(data)
result_lens = []

for i in range(n):
    for j in range(i+1, n):
        pair_width = abs(i - j)
        if data[i] < data[j]:
            pair_height = data[i]
        else:
            pair_height = data[j]
        result_lens.append(pair_height*pair_width)


print(max(result_lens))

Этот алгоритм был самый рабочий из всех остальных, но вот как уменьшить потребление памяти - я тут не знаю. Использование сторонних библиотек запрещено

python

Answer 1

[Rsa97]

1. Чтобы найти максимум, не надо запоминать все значения, достаточно помнить максимальное.
2. Эта задача решается гораздо проще со сложностью O(n), а не O(n²), как у вас.
Берём два крайних отрезка (left = 0 и right = n-1), вычисляем площадь прямоугольника (right - left) * min(length[left], length[right]).
Учитывая, что при сдвиге границ к центру расстояние (right - left) уменьшается, для увеличения площади необходимо увеличение min(length[left], length[right]). Поэтому берём ту границу left или right, длина отрезка для которой меньше, и начинаем двигать к центру, пока длина нового отрезка не станет больше предыдущей (length[left'] > length[left] или length[right'] > length[right]).
Вычисляем новую площадь. Если она больше предыдущей, запоминаем положения отрезков. Повторяем процедуру сдвигания.

Answer 2

[Данила]

Убираем создание списка result_lens, чтобы не сохранять промежуточные результаты.
Вместо этого вычисляем площадь каждой пары на лету и сразу же обновляем значение максимальной площади в переменной max_area.
Убираем ненужное копирование списка data_copy.

Для понимания изначально сложность алгоритма по памяти составляла O(n^2), но поскольку мы оптимизировали алгоритм, убрав сохранение промежуточных данных в список и используя одну лишь переменную для хранения максимальной площади, сейчас сложность составляет O(1)

length = input().split()
data = [int(x) for x in length]

n = len(data)
max_area = 0

for i in range(n):
    for j in range(i + 1, n):
        pair_width = abs(i - j)
        pair_height = min(data[i], data[j])
        max_area = max(max_area, pair_height * pair_width)

print(max_area)

Comments

[U235U235]

abs тоже не нужен, j-i просто.