House Robber in a Circle

The Idea

On a circle the only new rule is that the first and last houses touch. Rather than invent a recurrence for it, forbid one of them: solve the line without the last house, solve it again without the first, and keep the better. Every legal circular plan misses at least one end, so one of those two runs contains it.

Real-World Example

Ad slots around a rotating carousel, where neighbouring slots may not sell to the same advertiser. The last slot wraps back to the first, so the booking tool prices the strip twice — once ignoring the final slot, once ignoring the opening one.

The Code

def rob_line(vals):
    take, skip = 0, 0
    for v in vals:
        take, skip = skip + v, max(skip, take)   # take v, or keep the best so far
    return max(take, skip)

houses = [2, 7, 9, 3, 1]

print(rob_line(houses))                                     # 12 on a line
print(max(rob_line(houses[:-1]), rob_line(houses[1:])))     # 11 on a circle

def rob_line(vals):
  take, skip = 0, 0
  for v in vals:
      take, skip = skip + v, max(skip, take)
  return max(take, skip)

houses = [6, 1, 1, 6]
print(max(rob_line(houses[:-1]), rob_line(houses[1:])))