Оптимальная выручка при ежедневном производстве товаров

Условие

Дан массив из N положительных целых чисел, где каждый элемент обозначает цену одной единицы товара в соответствующий день. Каждый день мы выпускаем ровно одну единицу продукции и можем хранить её на складе неограниченное время. Необходимо определить наибольшую возможную суммарную выручку от всех произведённых товаров, при условии, что к концу N‑го дня весь запас должен быть полностью реализован.

Пример: 1 3 1 2 → 10

Ответ

Каждую единицу выгодно продавать по максимальной цене среди дня её выпуска и всех последующих дней. Поэтому ответ равен сумме суффиксных максимумов массива цен.

def max_revenue(prices):
    best_price = 0
    total = 0
    for price in reversed(prices):
        best_price = max(best_price, price)
        total += best_price
    return total

Для [1, 3, 1, 2] лучшие цены продажи — [3, 3, 2, 2], сумма 10. Единицы независимы, потому что хранение бесплатно, вместимость не ограничена и за день можно продать любое количество. При иных ограничениях этот жадный алгоритм уже не обоснован. Время O(n), дополнительная память O(1).