House Robber

Problem

Security audit systems model access patterns as sequences of locked vaults where triggering adjacent alarms invalidates both entries. You are given an array of non-negative integers representing the value in each house. Return the maximum amount you can rob without robbing two adjacent houses.

Example 1:

Input: [5, 1, 3, 9]
Output: 14
Explanation: Rob index 0 and 3: 5+9.

Example 2:

Input: [6, 3, 10, 7, 4]
Output: 20
Explanation: Rob index 0, 2, 4: 6+10+4.

Example 3:

Input: [4, 8, 5, 8, 2, 7]
Output: 23
Explanation: Rob index 1, 3, 5: 8+8+7.

Constraints:

• 1 <= nums.length <= 200
• 0 <= nums[i] <= 1000

Verification

Trace [6, 3, 10, 7, 4]: prev_two=6, prev_one=7. Index 2: current=max(7, 6+10)=16, prev_two=7, prev_one=16. Index 3: current=max(16, 7+7)=16, prev_two=16, prev_one=16. Index 4: current=max(16, 16+4)=20, prev_two=16, prev_one=20. Return 20.

Solution Breakdown

Approach: Decision DP (include/exclude) collapsed to two rolling variables.

At each house you make a binary choice: rob it or skip it. Robbing house i forbids robbing i-1, so the best total that includes house i is nums[i] plus the best you could do up through house i-2. Skipping house i keeps the best total through i-1 unchanged. The recurrence is therefore dp[i] = max(dp[i-1], dp[i-2] + nums[i]) - the larger of "skip" and "rob plus the safe earlier subtotal". Optimal substructure is what makes keeping only the running max correct: the best answer for a prefix can never be beaten by having carried a worse earlier subtotal. Because each step looks back exactly two positions, the array collapses to two scalars: prev_two (best through i-2) and prev_one (best through i-1). The base cases seed them - prev_two = nums[0] and prev_one = max(nums[0], nums[1]) - then each iteration computes current = max(prev_one, prev_two + nums[index]) and slides both forward. Trace [6,3,10,7,4]: the window walks 6,7 -> 16 -> 16 -> 20, returning 20, which is robbing houses 0, 2, 4 (6 + 10 + 4).

Edge cases: An empty list returns 0 and a single house returns nums[0]; both are handled before the loop, so the nums[1] access while seeding prev_one is always safe.

Complexity: O(n) time, O(1) space - one pass updating two scalars instead of an n-sized array.