LC 0213 [M] House Robber II - ALawliet/algorithms GitHub Wiki
class Solution:
def rob(self, nums):
def houserobber1(nums):
i1, i2 = 0, 0 # [i-1], [i-2]
for num in nums:
i1, i2 = i2, max(i1 + num, i2)
return i2
# assuming [-1][0,1,2,-1]
# if we choose [0], then we cannot take [-1] or [1], so we start at [2] up to [-1] (excluding the last) = [0,2]
# or if we do not choose [0], then we can choose from [1] to end (including the last and having it circle around) = [1,-1]
return max(nums[0] + houserobber1(nums[2:-1]), houserobber1(nums[1:]))
# this seems less intuitive
# 1) choose [0] = [0]
# 2) or choose from [1] to end (inclusive) = [1,-1]
# 3) or choose from [0] to end (non-inclusive) = [0,2]
# return max(nums[0], houserobber1(nums[1:]), houserobber1(nums[:-1]))