📑 题目：213. 打家劫舍 II

🚀 本题 LeetCode 传送门

题目大意

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

解题思路

• 这一题是第 198 题的加强版。不过这次是在一个环形的街道中，即最后一个元素和第一个元素是邻居，在不触碰警报的情况下，问能够窃取的财产的最大值是多少？
• 解题思路和第 198 完全一致，只需要增加额外的一个转换。由于首尾是相邻的，所以在取了第一个房子以后就不能取第 n 个房子，那么就在 [0,n - 1] 的区间内找出总价值最多的解，然后再 [1,n] 的区间内找出总价值最多的解，两者取最大值即可。

代码

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])
 }
 // 由于首尾是相邻的，所以需要对比 [0，n-1]、[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
}