House Robber

Given a list of non-negative integers representing money in houses along a street, return the maximum amount you can rob without robbing adjacent houses. A naive subset search is exponential.

Why this is worth learning

The final house is either skipped or taken. Taking it forbids exactly the previous house, so only two optimal prefix values are needed—not a remembered list of greedy choices.

Before coding: one-minute experiment

For [2,7,9,3,1], give the optimal totals after each prefix. Which houses achieve the final answer?

Function signature

func Rob(nums []int) int

Inputs / outputs

• nums: money in each house.
• Return: maximum loot without adjacent picks.

Example

nums = [2,7,9,3,1]
Best: 2 + 9 + 1 = 12
Output: 12

Constraints

• 0 <= len(nums) <= 100_000
• House amounts are nonnegative, and the maximum obtainable total is guaranteed to fit the target Go int.

Core idea (near-solution)

At each house, decide to take it (add to best up to i-2) or skip it (best up to i-1).

Invariant: prev1 is best up to i-1, prev2 is best up to i-2.

Algorithm (step-by-step)

1. Initialize prev2 = 0, prev1 = 0.
2. For each value v:
   • cur = max(prev1, prev2 + v).
   • Shift prev2 = prev1, prev1 = cur.
3. Return prev1.

Correctness sketch

For the first i houses, let R(i) be the maximum total from a nonadjacent subset, allowing the empty subset. Every feasible subset either omits house i-1, bounded by R(i-1), or includes it, leaving an optimal subset of the first i-2 houses worth R(i-2)+value. Both alternatives are feasible, so their maximum is exactly R(i). Empty-prefix bases are zero. Before each iteration, prev1 and prev2 store the preceding two optimal prefix values; computing before shifting preserves them. Induction yields the optimum for the full line.

Trace (hand walkthrough)

Example input:
nums = [2,7,9,3,1]
Best: 2 + 9 + 1 = 12
Output: 12

Walk:
- dp: [2,7,11,11,12] from nums [2,7,9,3,1]
- best = 12

Pitfalls to avoid

• Forgetting empty input case (return 0).
• Using O(n) DP when rolling variables suffice.

Debugging lens

Test empty, one-house, all-zero, and alternating high-value inputs. Do not overwrite the two-back state before computing take. Accumulated sums must fit int; a length bound alone does not guarantee that.

Complexity

• Time: O(n).
• Extra space: O(1).

Implementation notes (Go)

• Use int for sums; values are non-negative.

Contract precision

With nonnegative amounts, every candidate considered by the recurrence is a feasible robbery total and is at most the guaranteed representable maximum. No checked-overflow result is exposed for inputs outside that domain.

Reconstruction checkpoint

For [2,7,9,3,1], give the optimal totals after each prefix. Which houses achieve the final answer?

Return to 1D DP (Including Kadane) · Module quiz