House Robber Around a Circle
Problem
Houses sit in a circle (the last house is adjacent to the first). Each house holds some money. Picking two adjacent houses on the circle triggers an alarm. Maximize the total money taken.
Trick: the first and last house can never both be taken. So solve two linear subproblems — best across houses 0..n−2, and best across houses 1..n−1 — and return the larger. Each linear subproblem is the classic non-adjacent DP: dp[i] = max(dp[i−1], dp[i−2] + nums[i]).
Input
nums = [3, 7, 4, 9, 1]Output
16Take houses 1 (7) and 3 (9). They are not adjacent, and together they sum to 16.
def rob(nums):
n = len(nums)
if n == 1:
return nums[0]
def linear(lo, hi):
p2 = p1 = 0
for i in range(lo, hi + 1):
cur = max(p1, p2 + nums[i])
p2, p1 = p1, cur
return p1
return max(linear(0, n - 2), linear(1, n - 1))function rob(nums) {
const n = nums.length;
if (n === 1) return nums[0];
function linear(lo, hi) {
let prev2 = 0, prev1 = 0;
for (let i = lo; i <= hi; i++) {
const cur = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1; prev1 = cur;
}
return prev1;
}
return Math.max(linear(0, n - 2), linear(1, n - 1));
}class Solution {
int[] a;
public int rob(int[] nums) {
a = nums;
int n = nums.length;
if (n == 1) return nums[0];
return Math.max(linear(0, n - 2), linear(1, n - 1));
}
int linear(int lo, int hi) {
int p2 = 0, p1 = 0;
for (int i = lo; i <= hi; i++) {
int cur = Math.max(p1, p2 + a[i]);
p2 = p1; p1 = cur;
}
return p1;
}
}int linear(vector<int>& nums, int lo, int hi) {
int p2 = 0, p1 = 0;
for (int i = lo; i <= hi; i++) {
int cur = max(p1, p2 + nums[i]);
p2 = p1; p1 = cur;
}
return p1;
}
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
return max(linear(nums, 0, n - 2), linear(nums, 1, n - 1));
}