Rob houses in a circle without hitting two neighbours. The first and last touch, so run House Robber twice: once without each end.
▼The problem
LeetCode 213 (Medium). Houses stand in a circle, so the first and the last house are neighbours; nums[i] is the cash in house i. Robbing two neighbouring houses sets off the alarm. Return the most you can rob.
Examples (LeetCode's): [2,3,2] → 3 (the two 2s are neighbours on the ring), [1,2,3,1] → 4 (1 + 3) and [1,2,3] → 3 (1 and 3 are neighbours on the ring, so only the 3).
The solution
def rob(nums):
if len(nums) == 1:
return nums[0]
return max(line(nums, 0, len(nums) - 1),
line(nums, 1, len(nums)))
def line(nums, lo, hi):
prev, cur = 0, 0
for i in range(lo, hi):
prev, cur = cur, max(cur, prev + nums[i])
return curTranscript
House Robber Two. Same street rule as episode one, but the street is now a ring. Each house holds some cash, and robbing two neighbors sets off the alarm. On a ring, the first and last houses are neighbors too. What's the most you can take?
Take two, three, two: the twos touch, so the best is three. One, two, three, one gives four: one plus three. And one, two, three gives three, because one and three are now next door.
The tempting move: plain House Robber on the whole row. On two, three, two it grabs both twos for four. But the ends touch, so the alarm goes off.
The fix: the first and last house can never both be robbed. So break the circle twice. Once without the last house, once without the first. Each is a plain street; keep the bigger haul.
In code, line keeps two numbers: prev, the best haul two houses back, and cur, the best so far. Each house, cur becomes the bigger of skipping it, or its cash plus prev. Rob returns the max of both lines, and a single house is just its cash.
Back to one, two, three, one. Without the last house: one, then two, then three plus one is four. Without the first: two, then three, then one plus two only ties three. Four beats three. The answer is four.
Two passes, so order n time, and just two numbers: order one space.
Break the ring, rob two streets, keep the best. That's House Robber Two.