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.

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

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

• Invariant: prev1 is best up to i-1, prev2 is best up to i-2.
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

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.

Complexity

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

Implementation notes (Go)

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