The scrap copper spread

A scrap yard chalks one copper price on the gate board every morning. You have room in the shed for a single tonne, and one chance to buy it and sell it.

The problem

prices[i] is the price per tonne of scrap copper on day i, in rupees, and the days come in order. You may buy one tonne on one day and sell it on a strictly later day — no selling before you buy, no holding two tonnes, no second trade.

Report the largest profit available. If every ordered pair of days loses money, report 0: the yard leaves the shed empty that fortnight.

Input. prices — a list of integers, one price per day, in order.

Output. The largest prices[j] - prices[i] over pairs with i < j, or 0 if no such difference is positive.

Example.

prices = [82, 45, 61, 40, 58, 93, 51]  ->  53

Buy on day 3 at 40, sell on day 5 at 93. Buying on day 1 at 45 makes only 48 into the same peak, and selling on day 6 at 51 throws away 42.

A second example, where the cheapest day is worthless:

prices = [70, 66, 51, 47, 30]  ->  0

The board only falls, so the cheapest day is the last one and nothing is left to sell into. Every legal pair loses money, so the answer is 0, not −4.

Constraints.

• 1 <= len(prices) <= 10^5
• 0 <= prices[i] <= 10^6
• Prices may repeat, and may stay flat for many days.

Hints

Approach

Brute force

Try every pair of days with the buy first: n(n-1)/2 subtractions. Fine for a year of prices; about 5 × 10⁹ operations for 10⁵ days.

The insight

For any selling day, the only buying day worth considering is the cheapest one before it, so a single carried number replaces the entire inner loop.

The profit on day j is prices[j] - prices[i]. While the scan sits on day j, prices[j] is fixed, so maximising profit means minimising prices[i] over i < j — a prefix minimum, which is itself a one-pass quantity: each new day either beats it or leaves it alone, and none can undo it, because the prefix only grows. Walking left to right hands you exactly the prefix that i < j asks for, so the ordering never has to be checked.

Algorithm

1. Set cheapest = prices[0] and best = 0.
2. For each price from day 1 onward:
3. Score it: best = max(best, price - cheapest).
4. Then update: cheapest = min(cheapest, price).
5. Return best.

Complexity

Time O(n) — one pass, one subtraction and two comparisons per day. Space O(1) — two integers, whatever the length of the board.

Solution

"""The scrap copper spread — one pass carrying the cheapest day so far."""


def solve(prices):
    if not prices:
        return 0
    cheapest = prices[0]
    best = 0
    for price in prices[1:]:
        # invariant: `cheapest` is the minimum over strictly earlier days, so
        # scoring before updating keeps the buy strictly before the sell.
        if price - cheapest > best:
            best = price - cheapest
        if price < cheapest:
            cheapest = price
    return best

TESTS = [
    (([82, 45, 61, 40, 58, 93, 51],), 53),
    (([70, 66, 51, 47, 30],), 0),
    (([10, 90, 5, 20],), 80),
    (([93, 20],), 0),
    (([40],), 0),
    (([7, 7, 7, 7],), 0),
    (([1, 1000000],), 999999),
]

Pitfalls

• Starting best at the first difference instead of 0. On a falling board like [70, 66, 51, 47, 30] the best legal pair is −4, and returning it tells the yard to buy a tonne and lose money. Not trading is always available, so 0 is the floor.
• Subtracting the global minimum from the global maximum. On [93, 20] that reports 73 from a sale that happens before the purchase. The answer is 0.
• Resetting best when a new cheapest day appears. In [10, 90, 5, 20] the cheapest day arrives after the profitable one, and the 80 already banked must survive. Dropping it returns 15.

Variants

• Glasshouse spread — carries two running extremes instead of one, and the pair is unordered, so the direction of the difference stops mattering.
• Reaching the last swap station — the same carried state, but the number is a reach into the future rather than a fact about the past.