Overview

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you from robbing every house is that adjacent houses have security systems connected — if two adjacent houses are broken into on the same night, the police will be alerted.

Given an array nums representing the amount of money in each house, return the maximum amount you can rob without alerting the police (i.e., without robbing two adjacent houses).

Implement robHouses(nums).

Constraints

• 0 ≤ nums.length ≤ 100
• 0 ≤ nums[i] ≤ 400
• You cannot rob two adjacent houses.
• Aim for $O(n)$ time, $O(1)$ space.

Examples

robHouses([1, 2, 3, 1]);
// → 4  — rob house 0 (1) + house 2 (3)

robHouses([2, 7, 9, 3, 1]);
// → 12  — rob house 0 (2) + house 2 (9) + house 4 (1)

robHouses([2, 1, 1, 2]);
// → 4  — rob house 0 (2) + house 3 (2)

Notes

• Classic DP: at each house, decide to rob it (add its value to the max up to two houses back) or skip it (carry forward the max from the previous house).
• dp[i] = max(dp[i-1], dp[i-2] + nums[i])
• Only two variables needed — no array required.

Solution

function robHouses(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];

  let prev2 = 0;
  let prev1 = 0;

  for (const num of nums) {
    const curr = Math.max(prev1, prev2 + num);
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}

Resources

• House Robber — LeetCode
• Dynamic Programming — Wikipedia