Задача на вычисление площади прямоугольника из заборов

Question

Дано n-ое кол-во заборов с одинаковым расстоянием друг от друга - 1, каждый из которых расположен на одной линии, и имеет разную длину. Нужно вычислить максимально возможную площадь образованного прямоугольника из заборов. Притом можно не использовать забор полностью, но нельзя его удлинять. Есть следующее решение:

def max_rectangle_area(length):
    n = len(length)
    max_area = 0
    for i in range(0, n):
        for j in  range(i+1, n):
            fence = length[i]
            fence_2 = length[j]
            if fence >= fence_2:
                area = fence_2*(j-i)
            else:
                area = fence*(j-i)
            if area > max_area:
                max_area = area

    return max_area


if __name__ == '__main__':
    print('Введите длину каждого забора через пробел:')
    fences = [int(x) for x in input().split(' ')]
    print(max_rectangle_area(fences))

Вопрос: как можно его улучшить/изменить, чтобы минимизировать использование памяти? upd: Примерное изображение для наглядности.

Answer 1

Всем спасибо, оказывается много кушал банальный

print('Введите длину каждого забора через пробел:')

Answer 2

Вот этот код, как и Ваш у меня на ноуте работает мгновенно! Оба! Никакие памяти никто не ест. Даже измерить ничего нельзя - просто нет на это времени, всё уже заканчивается. Я это место в задании до сих пор понять не могу. О том, насколько код этой готовой консольной утилитки "лучше", судите сами (жуткий input() и обработку результатов ввода я не менял):

import os

def max_rectangle_area(length):
    stack = []
    max_area = 0
    index = 0

    while index < len(length):
        if not stack or length[stack[-1]] <= length[index]:
            stack.append(index)
            index += 1
        else:
            top_of_stack = stack.pop()
            area = (length[top_of_stack] * ((index - stack[-1] - 1) if stack else index))
            max_area = max(max_area, area)

    while stack:
        top_of_stack = stack.pop()
        area = (length[top_of_stack] * ((index - stack[-1] - 1) if stack else index))
        max_area = max(max_area, area)

    return max_area

if __name__ == '__main__':
    print('Введите длину каждого забора через пробел:')
    fences = [int(x) for x in input().split(' ')]
    print(max_rectangle_area(fences))

os.system("pause")

БЛОГ НА HUSL

Задача на вычисление площади прямоугольника из заборов

Ответы (2 шт):