Copper at the weighbridge

A scrap yard chalks one copper price on the board each morning. The dealer can buy or sell at that price, and the weighbridge takes a fixed cut every time a lot leaves the gate.

The problem

The board shows one price per lot, one price per day, for a run of days. On any day the dealer may buy a lot at that day's price, or sell the lot they are holding at that day's price, or do neither. The yard has room for one lot at a time, so a purchase is only allowed when the shed is empty, and a sale only when it is not. Buying and selling on the same day is allowed and pointless.

Every completed sale pays a fixed toll to the weighbridge, charged once, when the lot goes out. Buying costs nothing beyond the price.

The dealer starts with an empty shed and must finish with one: copper left in the shed at the end of the run is worth nothing. Work out the largest profit the run can make. If no set of trades makes money, the answer is 0 — doing nothing is always allowed.

Input. prices — a list of integers, the price per lot on each day, in order. toll — an integer, the weighbridge charge on each completed sale.

Output. The largest profit over the whole run.

Example.

prices = [12, 20, 9, 15, 22], toll = 3   ->  15

Buy at 12 and sell at 20 for 8 less the toll, then buy at 9 and sell at 22 for 13 less the toll: 5 + 10 = 15.

A second example, where raising the toll merges the trades away:

prices = [12, 20, 9, 15, 22], toll = 9   ->  4

The first trade now earns 8 and costs 9, so it is dropped. Only buying at 9 and selling at 22 survives, at 13 less 9. Holding from 12 through to 22 pays 10 less 9, which is worse.

Constraints.

• 0 <= len(prices) <= 5 · 10^4
• 1 <= prices[i] <= 10^5
• 0 <= toll <= 10^5

Hints

Approach

Brute force

Every day offers up to three moves, so trying them all is 3^n sequences — 10^23 for a fifty-day run, and the constraint allows a thousand times that many days. Enumerating sets of disjoint buy-and-sell day pairs is no better.

The insight

The entire trading history collapses into one bit — is there a lot in the shed this morning — so two running balances stand in for every history.

Nothing in the rules refers to when a lot was bought or what it cost: a sale pays today's price less the toll whatever came before. So two histories in the same state have identical futures, and only their balances differ. That is the precondition for keeping just the best of each. On each day, holding = max(holding, empty - price) and empty = max(empty, holding + price - toll).

Algorithm

1. If the run is empty, return 0.
2. Set holding = -prices[0] and empty = 0.
3. For each later price: holding becomes the better of holding on and buying today out of empty; empty becomes the better of staying out and selling today's lot for price - toll.
4. Return empty at the end of the run — never holding, which still has unsold copper in it.

Complexity

Time O(n) — two comparisons per day. Space O(1); two integers, because the recurrence never looks back beyond yesterday's pair.

Solution

"""Copper at the weighbridge — two rolling balances, one toll per completed sale."""


def solve(prices, toll):
    if not prices:
        return 0
    # holding: most money the dealer can have with a lot in the shed.
    # empty:   most money the dealer can have with the shed clear.
    holding, empty = -prices[0], 0
    for price in prices[1:]:
        # Both are computed from yesterday's pair; a same-day buy and sell only
        # ever loses the toll, so reusing today's holding here is harmless.
        holding = max(holding, empty - price)
        empty = max(empty, holding + price - toll)
    return empty            # copper left in the shed is worth nothing

TESTS = [
    (([12, 20, 9, 15, 22], 3), 15),
    (([12, 20, 9, 15, 22], 9), 4),
    (([1, 3, 2, 8, 4, 9], 2), 8),
    (([21, 17, 14, 9], 2), 0),
    (([7], 4), 0),
    (([], 3), 0),
    (([5, 5, 5, 5], 0), 0),
]

Pitfalls

• Charging the toll on the buy as well as the sale. That doubles the cut, and on [12, 20, 9, 15, 22] with a toll of 3 it returns 9 instead of 15.
• Adding up every rise and subtracting a toll per rise. On the same run that gives (20-12-3) + (15-9-3) + (22-15-3) = 12. A rise held across two days is one trade and pays the toll once, which is where the missing 3 went.
• Indexing prices[0] on an empty run. A yard with no trading days is legal and the answer is 0, not an IndexError.

Variants

• The clearing day — the same two balances, plus a rule that bars buying the day after a sale.
• Linear DP — the rolling-state recipe this sweep is an instance of.