213.打家劫舍 II

打家劫舍 II

所有的房屋都围成一圈。相邻的房屋装有防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定数组 nums 代表每个房屋存放金额，计算不触动警报的情况下能偷到的最高金额。

解析

环形问题拆分成两个线性问题：偷 [0, n-2] 和偷 [1, n-1]，取较大值。

var rob = function (nums) {
  if (nums.length === 1) return nums[0];
  function robRange(lo, hi) {
    let prev2 = 0, prev1 = 0;
    for (let i = lo; i <= hi; i++) {
      const curr = Math.max(prev1, prev2 + nums[i]);
      prev2 = prev1; prev1 = curr;
    }
    return prev1;
  }
  return Math.max(robRange(0, nums.length - 2), robRange(1, nums.length - 1));
};