Problem Statement

You are given an array representing the amount of money each house has. This array models a circle of houses, meaning that the first and last houses are adjacent. You are tasked with figuring out the maximum amount of money you can rob without alerting the neighbors.

The rule is: if you rob one house, you cannot rob its adjacent houses.

Examples

Example 1:

• Input: [4, 2, 3, 1]
• Expected Output: 7
• Justification: Rob the 1st and 3rd house, which gives 4 + 3 = 7.

Example 2:

• Input: [5, 1, 2, 5]
• Expected Output: 7
• Justification: Rob the 1st and 3rd house, which gives 5 + 2 = 7.

Example 3:

• Input: [1, 2, 3, 4, 5]
• Expected Output: 8
• Justification: Rob the 3rd and 5th house, which gives 3 + 5 = 8.

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

Solution

The core idea of our algorithm is to split the circular house problem into two simpler linear problems and then solve each linear problem using a dynamic programming approach. Since the first and last houses in the circle are adjacent, we can't rob them both. Thus, we consider two scenarios: robbing houses excluding the first one and robbing houses excluding the last one. For each scenario, we use a helper function that returns the maximum amount we can rob. This helper function utilizes dynamic programming to keep track of the cumulative robbery amounts, ensuring that no two consecutive houses are robbed. Finally, our solution is the maximum of the two scenarios.

1. Edge Cases Handling: Begin by checking for edge cases:

   • If the input array is null or has a length of 0, return 0 since there are no houses to rob.
   • If there's only one house, return its value.
   • If there are two houses, return the maximum value of the two houses.

2. Two Scenarios Handling: Due to the circular structure, handle two scenarios:

   • Exclude the first house and compute for the rest.
   • Exclude the last house and compute for the others.

   Use a helper function to compute the maximum for each scenario.

3. Simple Robber Helper Function: This function calculates the maximum robbing amount for a linear set of houses using dynamic programming:

   • Maintain two variables, prevMax and currMax, to keep track of the max amount robbed up to the previous and current house, respectively.
   • Iterate through each house in the given range (based on the scenario). At each house, decide whether to rob it (in which case you can't rob the previous house) or skip it.
   • For each house, update currMax based on whether robbing the current house results in a larger amount than skipping it.

4. Return the Maximum: The main function concludes by returning the maximum value from the two scenarios.

Algorithm Walkthrough

Let's trace the third example, [1, 2, 3, 4, 5]. Move through the steps one at a time:

Code