167. House Robber II

Medium · Dynamic Programming

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle, meaning the first house is the neighbor of the last one. Additionally, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array `nums` where `nums[i]` is the amount of money in the `i`-th house, return the maximum amount of money you can rob without alerting the police (i.e., you cannot rob two adjacent houses).

The circular constraint means you cannot rob both the first and last house in the same robbery plan.

Examples

Example 1
Input: [1, 2, 3, 1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total = 1 + 3 = 4. You cannot rob houses 2 and 4 because they are adjacent to house 3 and house 1 respectively, and you cannot rob both house 1 and house 4 due to the circular constraint.
Example 2
Input: [2, 3, 2]
Output: 3
Explanation: Rob house 2 (money = 3). Total = 3. You cannot rob houses 1 and 3 together because they are adjacent to house 2, and you cannot rob both house 1 and house 3 due to the circular constraint.

Constraints