Pitches round the market ring

The Saturday market rings a green, and the fire officer wants a clear gap beside every van. The clerk still has a day's rent to bring in.

The problem

The pitches are numbered 1 to n clockwise round the green, and the ring closes: pitch n stands beside pitch 1. The clerk has a rent for each pitch — what a trader would pay for it.

The fire rule is one line. Two pitches next to each other cannot both be let, because an engine needs a lane through to the green. Pitches that are not neighbours may all be let. An empty pitch brings in nothing.

The clerk's job is to pick the pitches that bring in the most rent.

Input. rents — a list of integers in ring order, what each pitch would bring. The list may be empty.

Output. The most rent the day can take with no two neighbouring pitches let, counting the join from last pitch to first.

Example.

rents = [45, 15, 80, 25, 60]   ->  140

Let pitches 3 and 5: 80 + 60 = 140. Pitches 1, 3 and 5 would bring 185, but pitch 5 and pitch 1 stand side by side.

A second example, where the join does the damage:

rents = [95, 10, 20, 85]   ->  115

The two richest pitches are 1 and 4, and on a ring of four they touch. The best legal day lets pitches 1 and 3 for 115.

Constraints.

• 0 <= len(rents) <= 10^5
• 0 <= rents[i] <= 10^4
• With n = 2 the two pitches count as neighbours
• The answer fits in a 64-bit integer

Hints

Approach

Brute force

Try every set of pitches, drop any with a neighbouring pair, and keep the richest. That is 2^n sets — 10^6 at twenty pitches, hopeless at the 10^5 allowed.

The insight

Every legal day leaves pitch 1 or pitch n empty, so the ring becomes two straight rows: one with pitch n struck off, one with pitch 1 struck off.

The join is the only rule a straight sweep misses, and striking off either end removes it, so each row is an ordinary line. No row can produce an illegal day, since dropping a pitch only removes options, and every legal day survives in one row or the other. The larger sweep is the answer.

Algorithm

1. Return 0 on an empty ring, and the single rent on a ring of one: that pitch has no neighbour, and both rows would be empty.
2. Sweep pitches 0 .. n-2 with two running totals read from the previous pair: taken = empty + rent and empty = max(empty, taken).
3. Sweep pitches 1 .. n-1 the same way.
4. Return the larger of the two sweeps.

Complexity

Time O(n) — two passes, constant work per pitch. Space O(1); two running totals per sweep, with rents read by index, never sliced.

Solution

"""Pitches round the market ring — the row sweep run twice on a ring cut at one pitch."""


def best_in_row(rents, start, stop):
    """Best no-two-neighbours rent over the pitches rents[start:stop]."""
    empty, taken = 0, 0
    for i in range(start, stop):        # by index, so no slice is copied
        # taken: this pitch is let, so the one before it was left empty.
        # empty: this pitch is empty, so either total behind it stands.
        empty, taken = max(empty, taken), empty + rents[i]
    return max(empty, taken)


def solve(rents):
    n = len(rents)
    if n == 0:
        return 0
    if n == 1:
        return rents[0]                 # no neighbour, and both rows would drop it
    # Pitch 1 and pitch n touch, so every legal day leaves one of them empty;
    # striking off either end turns the ring into an ordinary row.
    return max(best_in_row(rents, 0, n - 1), best_in_row(rents, 1, n))

TESTS = [
    (([45, 15, 80, 25, 60],), 140),
    (([95, 10, 20, 85],), 115),
    (([30, 5, 5, 70, 40],), 100),
    (([55, 90],), 90),
    (([140],), 140),
    (([],), 0),
    (([35, 35, 35],), 35),
    (([0, 0, 0, 0],), 0),
]

Pitfalls

• Sweeping the ring once as though it were a row. On [95, 10, 20, 85] that lets pitches 1 and 4, which touch: 180, not 115.
• Forgetting the single pitch. With rents = [140] both rows are empty, so a bare max of the sweeps returns 0, not 140.
• Striking off the cheaper of the two end pitches. On [30, 5, 5, 70, 40] dropping the 30 returns 75, while dropping the 40 returns 100, the answer.

Variants

• Booking the soundstages — the same neighbour rule on a row that never closes: one sweep settles it.
• The clearing day — a one-step rule met with a third state instead of a second pass.