Best haul without opening two neighbouring lockers

Dynamic programming Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
amounts = [2, 1, 1, 2]
prev2 = prev1 = 0
for a in amounts:
    prev2, prev1 = prev1, max(prev1, prev2 + a)
print(prev1, sum(amounts[::2]), sum(amounts[1::2]))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 4 3 3

Right: opening the first and last lockers beats both every-other patterns.

The DP considers every allowed pattern implicitly, including gaps of two, which fixed patterns miss.

Why not the others?
  • B 3 3 3. Lockers 0 and 3 are not neighbours, giving 4.
  • C 6 3 3. Opening all four breaks the neighbour rule.

30-second answer

For each locker, either skip it (keep the best so far) or open it (its amount plus the best up to two lockers back). Two running values are enough: best through the previous locker and best through the one before. O(n) time and O(1) memory.

Practise saying it · 45 s. No recording, just a timer

Explain the no-neighbours DP.

Say your answer out loud, then check which of these points you covered:

  • Take or skip
  • best = max(skip, take + two back)
  • O(1) memory

Deep dive

The take-or-skip recurrence is the template for 'no two adjacent' questions.

Rolling two variables is the standard memory saving for 1-D DP that looks two cells back.

Amounts are non-negative here; with negatives, skipping everything (0) stays allowed.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def best_haul(amounts: list[int]) -> int:
    two_back = one_back = 0  # best totals two and one lockers ago
    for a in amounts:
        two_back, one_back = one_back, max(one_back, two_back + a)
    return one_back

Common mistakes

  • Taking every other locker, which fails on [2, 1, 1, 2].
  • Updating the two variables in the wrong order.

Senior take & follow-ups

Point out the 'every other locker' trap with a counterexample.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if the lockers form a ring?

    Show hint

    Solve twice: without the first locker and without the last, and take the better.

  2. How do you list the lockers opened?

    Show hint

    Keep the full table and walk back, checking which choice gave each value.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.