Basically DP. Store the max attainable by robbing up to each of the previous two houses (prevprev and prev); then you can either:
- don't rob the current house, in which case you can get the value up to the previous house, or
- rob the current house, in which case the max is its value plus the max for two houses back.
def rob(self, nums): prevprev = 0 prev = 0 for i in xrange(len(nums)): tmp = prev prev = max(nums[i]+prevprev, prev) prevprev = tmp return prev