The clearing day

The grain exchange calls one price for barley each morning. A merchant may take a lot or let one go, but never buy the day after a sale.

The problem

One price is called per day. The merchant may buy one lot at that price, sell the lot they hold, or stand aside. Only one lot may be held at a time.

The day after any sale is a clearing day: on it the merchant may not buy, though the day after that is open again. Selling is never blocked, since a sale needs a lot already in store. A lot still held at the end is worth nothing, and standing aside all run is allowed, so the answer is never negative.

Input. prices — a list of integers, the price called on each day, in order.

Output. The largest profit over the whole run.

Example.

prices = [8, 14, 6, 9, 13]   ->  10

Buy at 8, sell at 14 for 6. Day three is a clearing day, so the 6 is out of reach. Buy at 9, sell at 13 for 4: 10 in all. Without the rule the run pays 13.

A second example, where one long hold beats two short trades:

prices = [5, 9, 8, 12]   ->  7

Selling at 9 blocks the buy at 8, leaving 4. Holding from 5 to 12 pays 7.

Constraints.

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

Hints

Approach

Brute force

Three moves a day gives 3^n sequences: 3^50 is 7.2 · 10^23, and a run may run a thousand times longer. Discarding the illegal ones afterwards does not shrink the enumeration.

The insight

The clearing rule reaches exactly one day back, so splitting "holding nothing" into "sold today" and "did not sell today" makes today's best depend only on yesterday's three numbers.

With two states the sweep cannot tell a free morning from a clearing morning, so it buys on the clearing day. The third state restores what the recurrence needs: within one state every history has the same future, so keeping the richest is safe.

Algorithm

1. Return 0 on an empty run.
2. Set hold = -prices[0], sold = 0, free = 0.
3. For each later price, take all three from the previous triple in one step: hold = max(hold, free - price), sold = hold + price, free = max(free, sold).
4. Return max(sold, free) — the two states that end with no barley.

Complexity

Time O(n) — two comparisons and two additions per day. Space O(1); three integers, with prices read by index rather than copied.

Solution

"""The clearing day — three rolling states, because a sale bars buying tomorrow."""


def solve(prices):
    if not prices:
        return 0                        # no days called, so nothing to trade
    # Read at the close of the day:
    # hold: best balance with a lot in store.
    # sold: best balance where the sale happened today, so tomorrow is a clearing day.
    # free: best balance with no lot and no sale today, so tomorrow buying is open.
    hold, sold, free = -prices[0], 0, 0
    for i in range(1, len(prices)):     # by index: prices is never copied
        price = prices[i]
        # All three come from yesterday's triple: buying today may only build on
        # "free", never on a sale made today or yesterday.
        hold, sold, free = max(hold, free - price), hold + price, max(free, sold)
    return max(sold, free)              # a lot still in store is worth nothing

TESTS = [
    (([8, 14, 6, 9, 13],), 10),
    (([5, 9, 8, 12],), 7),
    (([2, 7, 1, 9, 3, 11],), 13),
    (([9, 7, 5, 2],), 0),
    (([10, 1, 10, 1, 10],), 9),
    (([4],), 0),
    (([],), 0),
]

Pitfalls

• Reusing the two-state sweep from a market with no clearing rule. On [8, 14, 6, 9, 13] it buys at 6 the morning after the sale at 14: 13, not 10.
• Updating the three in sequence instead of together. Setting free = max(free, sold) before hold lets today's buy build on a sale made today — the clearing day ignored, and [8, 14, 6, 9, 13] returns 13 again.
• Seeding from prices[0] without checking for an empty run. The constraints allow no days at all, and -prices[0] raises IndexError on []. Return 0 first; a single day like [4] is worth 0 too.

Variants

• Copper at the weighbridge — two states and a charge per sale instead of a waiting day.
• Pitches round the market ring — another one-step rule, met with a second pass instead of a third state.