class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size(); 
        if (n < 2) return n ? nums[0] : 0;
        return max(robber(nums, 0, n - 2), robber(nums, 1, n - 1));
    }
private:
    int robber(vector<int>& nums, int l, int r) {
        int pre = 0, cur = 0;
        for (int i = l; i <= r; i++) {
            int temp = max(pre + nums[i], cur);
            pre = cur;
            cur = temp;
        }
        return cur;
    }
};

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1)    return nums[0];
        if(nums.length == 2)    return Math.max(nums[0], nums[1]);
        
        // 1st option: including the 1st and excluding the last house
        int resultWithFirst = solve(nums, 0, nums.length - 2);
        // 2nd option: excluding the 1st and including the last house
        int resultWithLast = solve(nums, 1, nums.length - 1);
        
        // Return the maximum of the two results
        return Math.max(resultWithFirst, resultWithLast);
    }
    
    public int solve(int[] nums, int start, int end){        
        if(start == end)    return nums[start];
        
        // Array to store the maximum sum at the current iteration
        // while traversing all houses
        int money[] = new int[nums.length];
        
        /* Base case */
        money[start] = nums[start];
        
        // At the 2nd house, we decide to rob
        // either the 1st house or the 2nd
        // This is the core idea of the transition function
        money[start + 1] = Math.max(nums[start + 1], nums[start]);
        
        for (int i = start + 2; i <= end; ++i)
            /* At ith house we have two options:
             1. not rob it, keeping the money from the (i-1)th house
             2. rob it after the (i-2)th house, skipping the (i-1)th house
              We choose the one that gives the max amount */
            money[i] = Math.max(money[i - 1], money[i - 2] + nums[i]);
        
        // Return the sum that we have at the last house
        return money[end];
    }
}
 

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def simple_rob(nums, i, j):
            rob, not_rob = 0, 0
            for idx in range(i, j):
                num = nums[idx]
                rob, not_rob = not_rob + num, max(rob, not_rob)
            return max(rob, not_rob)
        
        if not nums:
            return 0
        elif len(nums) == 1:
            return nums[0]
        else:
            n = len(nums)
            return max(simple_rob(nums, 1, n), simple_rob(nums, 0, n-1))