Codeforces 865D Buy Low Sell High - Implementation

Here is the solution. Use a min-heap to track all prices you might buy at, then greedily sell when profitable:

function maxProfit(prices)
    minHeap := empty min-heap
    profit := 0
    Each price p in prices
        push p to minHeap
        if p > minHeap.top()
            profit := profit + (p - minHeap.top())
            pop from minHeap
        push p to minHeap
    // Double push for retroactive adjustment
    return profit

Each price, push it to the heap. If the price exceeds the minimum in the heap, you can profit by selling. Pop the minimum, add the profit difference, then push the current price twice.

The double-push allows retroactive adjustment if a better opportunity comes later.

Time: $O(n \log n)$. Space: $O(n)$ for the heap.

Time: $O(n \log n)$. Space: $O(n)$.