House Robber II

Problem Description

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

PS: In real life, we should not think of robbery (^_^) as if we were thieves. We can think of this as a precaution to design the actual alarm system better!

Solution

I. Extend the previous solution
In the previous example, we can "rob" from the first house to the last house. In this example, we cannot "rob" the first and last house at the same time. So we can think simply that we can choose to "rob" from the second house to the last house, or "rob" from the first house to the second-last house.

Figure 1: Choose range of houses to "rob"!

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0: return 0
        if n < 4: return max(nums)

        first, second = 0, 0
        for i in nums[:-1]: first, second = second, max(first + i, second)
        result = second

        first, second = 0, 0
        for i in nums[1:]: first, second = second, max(first + i, second)
        return max(result, second)