213. House Robber II

Same as House Robber, but the houses form a circle, so the first and last houses are neighbors.

The first and last houses are neighbors, so at most one is robbed. Solve the line without the last house and the line without the first, then take the better one.

1function rob(nums: number[]): number {
2  if (nums.length === 1) return nums[0];
3  const line = (lo: number, hi: number) => {
4    let prev2 = 0, prev1 = 0;
5    for (let i = lo; i <= hi; i++) {
6      [prev2, prev1] = [prev1, Math.max(prev1, prev2 + nums[i])];
7    }
8    return prev1;
9  };
10  const a = line(0, nums.length - 2);
11  const b = line(1, nums.length - 1);
12  return Math.max(a, b);
13}

prev2 = 0prev1 = 0

houses (circle)

Without the last house: house 0 (2).

1 / 0

Space: play/pause · ←/→: step