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.

Input: [1, 2, 3, 1]      → 4   (rob index 0 and 2: 1+3)
Input: [2, 7, 9, 3, 1]   → 12  (rob index 0, 2, 4: 2+9+1)
Input: [2, 1, 1, 2]      → 4   (rob index 0 and 3: 2+2)

Verification

Trace [2, 7, 9, 3, 1]: prev_two=2, prev_one=7. Index 2: current=max(7, 2+9)=11, prev_two=7, prev_one=11. Index 3: current=max(11, 7+3)=11, prev_two=11, prev_one=11. Index 4: current=max(11, 11+1)=12, prev_two=11, prev_one=12. Return 12.

Solution

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 [2,7,9,3,1]: the window walks 2,7 -> 11 -> 11 -> 12, returning 12, which is robbing houses 0, 2, 4 (2 + 9 + 1).

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.