213. House Robber II

Problem

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. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

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.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

Problem Summary

You are a professional robber planning to rob houses along a street. Each house has a certain amount of cash stashed inside. All the houses in this place are arranged in a circle, which means the first house and the last house are next to each other. Meanwhile, adjacent houses have interconnected security systems, and if two adjacent houses are broken into on the same night, the system will automatically alert the police.

Given a non-negative integer array representing the amount of money stored in each house, calculate the maximum amount of money you can rob without triggering the alarm system.

Solution Approach

• This problem is an enhanced version of Problem 198. However, this time the street is circular, meaning the last element and the first element are neighbors. Without triggering the alarm, what is the maximum amount of property that can be robbed?
• The solution approach is exactly the same as Problem 198, requiring only one additional transformation. Since the first and last houses are adjacent, after taking the first house, you cannot take the nth house. So find the solution with the maximum total value in the interval [0,n - 1], then find the solution with the maximum total value in the interval [1,n], and take the maximum of the two.

Code

package leetcode

func rob213(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	if n == 1 {
		return nums[0]
	}
	if n == 2 {
		return max(nums[0], nums[1])
	}
	// Since the first and last houses are adjacent, compare the maximum values of the two intervals [0,n-1] and [1,n]
	return max(rob213_1(nums, 0, n-2), rob213_1(nums, 1, n-1))
}

func rob213_1(nums []int, start, end int) int {
	preMax := nums[start]
	curMax := max(preMax, nums[start+1])
	for i := start + 2; i <= end; i++ {
		tmp := curMax
		curMax = max(curMax, nums[i]+preMax)
		preMax = tmp
	}
	return curMax
}