[213] 打家劫舍 II

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

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

示例 1:

输入：[2,3,2]

输出：3

解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2:

输入：[1,2,3,1]

输出：4

解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。

偷窃到的最高金额 = 1 + 3 = 4 。

这道题与198. 打家劫舍长得几乎一致，因此解法也是相同的，解题思路可以参考该题。

本题与上题唯一的一点不同在于，房屋的摆放是环形的，形成了一个环形数组。因此我们做的最优决策里，不能同时取第一号和最后一号房屋里的钱。

解决方法也很简单，我们排除掉收尾连接处可能对结果产生的影响，即分别算出取 [1, n] 房间与 [0, n-1] 房间的最优决策，再比较一下取较大的那个即能得到最优解了。

function rob(nums: number[]): number {
  const len = nums.length;
  if (len === 1) return nums[0];

  // 围成一圈后，代表着不能同时抢第一家与最后一家
  // 需要分成抢第一家与不抢第一家两种情况
  const rob1 = getMaxSum(0, len - 1);
  const notRob1 = getMaxSum(1, len);
  return Math.max(rob1, notRob1);

  function getMaxSum(start: number, end: number) {
    let interval = 0;
    let prev = 0;
    for (let i = start; i < end; i++) {
      const res = Math.max(prev, interval + nums[i]);
      interval = prev;
      prev = res;
    }
    return prev;
  }
}