House Robber

The Idea

Values sit in a row and picking one forbids both of its neighbours. At every position ask a single question: take this value plus the best total that ended two positions back, or skip it and carry the best so far forward? Two running totals hold everything the decision needs, so no array of results is required.

Real-World Example

A touring singer is offered a fee for every night of a festival week, but the voice needs a full day of rest after each show — no two nights in a row. The fattest single fee is often the wrong pick, because taking it silences the two nights around it.

The Code

def rob(values):
    skip, take = 0, 0                              # best ending here: unused / used
    for v in values:
        skip, take = max(skip, take), skip + v     # taking v needs the previous skipped
    return max(skip, take)

print(rob([2, 7, 9, 3, 1]))   # 12
print(rob([5, 5, 10, 100, 10, 5]))   # 110

def rob(values):
  skip, take = 0, 0
  for v in values:
      skip, take = max(skip, take), skip + v
  return max(skip, take)

print(rob([5, 1, 1, 5]))