Daily Problem: LC 213 House Robber II
213. House Robber II
1 min readOct 14, 2020
Solution with comments in python3
class Solution:
def house_rob(self, nums):
if not nums:return 0
if len(nums) <=2:return max(nums)
rob, not_rob = 0, 0
ret = 0
for num in nums:
# not rob at this num will be: max( rob + 0, not_rob)
# 0 means not rob at this num
new_not_rob = max(rob, not_rob)
# new_rob will be old not rob + num
new_rob = not_rob + num
rob, not_rob = new_rob, new_not_rob
ret = max(ret, not_rob, rob )
return ret def rob(self, nums: List[int]) -> int:
if len(nums) <=2: return max(nums)
# we can not rob the first and the last at the same time. So the
# problem is change to either rob the 0 to n-2 inclusively
# or 1 to n-1 inclusively.
return max(self.house_rob(nums[:-1]), self.house_rob(nums[1:]))
