Booking the soundstages

A film lot rents its soundstages by the week, and the wall between two neighbours leaks noise. The booking sheet has to leave gaps.

The problem

The lot is one long corridor. Stages are numbered 1, 2, 3 and so on along it, and each pair of consecutive stages shares a wall. A production offers a fee for next week on the stages it wants, and the lot manager writes one number per stage: what that stage would earn.

A camera rolling in one stage picks up the hammering next door, so two stages that share a wall cannot both be booked in the same week. Stages that are not neighbours are free to run at once, however many of them there are. The corridor does not loop: stage 1 and the last stage are at opposite ends and share nothing.

Choose the set of stages to book so the week earns as much as possible.

Input. fees — a list of integers, the fee for each stage in corridor order. An empty corridor is allowed.

Output. The largest total fee from a set of stages containing no two neighbours.

Example.

fees = [90, 40, 130, 60, 110]   ->  330

Book stages 1, 3 and 5: 90 + 130 + 110 = 330. Booking the 130 and the 110 is worth only 240, and no legal set beats 330.

A second example, where the pattern is not alternating:

fees = [70, 10, 10, 90]   ->  160

The best sheet books the two ends and leaves a gap of two in the middle. Taking every other stage gives 80 or 100, and both are wrong.

Constraints.

• 0 <= len(fees) <= 10^5
• 0 <= fees[i] <= 10^4
• The answer fits in a 64-bit integer

Hints

Approach

Brute force

Enumerate every subset of stages, throw away the ones containing a neighbouring pair, and keep the richest survivor. That is 2^n subsets — 10^12 for a corridor of 40 stages, and the constraint allows 10^5.

The insight

Sweeping the corridor left to right, the whole history collapses into one question — is the stage I just passed booked? — so two running totals stand in for every sheet.

The rule is local: a booking is illegal only because of its immediate neighbours, never because of a stage further back. So once you know the best total for each answer to that question, nothing earlier can change what happens next. Booking stage i is legal exactly on top of a sheet that left stage i - 1 free, which gives booked = skipped + fees[i]; leaving stage i free is legal on top of either, which gives skipped = max(skipped, booked).

Algorithm

1. Start skipped = 0 and booked = 0 — an empty corridor earns nothing.
2. For each fee in order, compute both new values from the old pair: skipped' = max(skipped, booked) and booked' = skipped + fee.
3. Replace the pair and move to the next stage.
4. Return max(skipped, booked).

Complexity

Time O(n) — one comparison and one addition per stage. Space O(1); two integers, because the recurrence never reaches further back than one stage.

Solution

"""Booking the soundstages — linear DP with two rolling totals, no two neighbours."""


def solve(fees):
    # skipped: best total for the stages seen so far when the last one is free.
    # booked:  best total for the stages seen so far when the last one is booked.
    skipped, booked = 0, 0
    for fee in fees:
        # This stage is booked only on top of a corridor whose last stage was free.
        skipped, booked = max(skipped, booked), skipped + fee
    return max(skipped, booked)

TESTS = [
    (([90, 40, 130, 60, 110],), 330),
    (([70, 10, 10, 90],), 160),
    (([260],), 260),
    (([120, 120, 120, 120],), 240),
    (([40, 250, 60],), 250),
    (([],), 0),
    (([0, 0, 0],), 0),
]

Pitfalls

• Taking the biggest fee first and deleting its neighbours. On [50, 90, 60, 20, 80] that grabs 90, then 80, and stops at 170. The answer is 50 + 60 + 80 = 190, which never touches the largest number on the sheet.
• Assuming the booked stages alternate. [70, 10, 10, 90] needs a gap of two, and every-other-stage returns 100 instead of 160.
• Updating the two totals one after the other. Writing skipped = max(skipped, booked) and then booked = skipped + fee feeds the new skipped into booked and books two neighbours: [90, 40] returns 130 instead of 90. Compute both from the previous pair.

Variants

• Standing the pipe rank — the same recurrence after the corridor is bent into a circle, so the two ends become neighbours.
• Linear DP — where the "carry a fixed number of rolling values" recipe comes from.