House Robber II

Houses are in a circle, so the first and last are adjacent. Return the maximum amount you can rob without robbing adjacent houses. A naive search over subsets is exponential.

Function signature

func RobII(nums []int) int

Inputs / outputs

• nums: money in each house.
• Return: maximum loot without adjacent picks.

Example

nums = [2,3,2]
Either take house 0 or 2, but not both.
Output: 3

Constraints

• 0 <= len(nums) <= 100_000

Core idea (near-solution)

You cannot take both first and last. Solve two linear subproblems:

• Rob houses [0..n-2]
• Rob houses [1..n-1]

Take the max of the two.

Invariant: each subproblem is the standard House Robber DP.

Algorithm (step-by-step)

1. Handle n=0 and n=1.
2. Compute robLine(nums[:n-1]) and robLine(nums[1:]).
3. Return the max.

Correctness sketch

• Invariant: each subproblem is the standard House Robber DP.
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

Trace (hand walkthrough)

Example input:
nums = [2,3,2]
Either take house 0 or 2, but not both.
Output: 3

Walk:
- rob 0..1 -> max(2,3)=3
- rob 1..2 -> max(3,2)=3
- answer 3

Pitfalls to avoid

• Treating it as a linear street (would allow picking both ends).
• Forgetting small n edge cases.

Complexity

• Time: O(n).
• Extra space: O(1).

Implementation notes (Go)

• Reuse the linear robber helper with rolling variables.