Houses are lined up in a row, each holding some amount of money in nums. You can't rob two adjacent houses (it trips the alarm). Return the most money you can rob without robbing two neighbors.
Example
Input nums = [1,2,3,1]
Output 4
Key Pointers
At each house there are exactly two choices: skip it (carry forward the best total through the previous house), or rob it (its value plus the best total through two houses back).
Because adjacent houses can't both be robbed, the best total through house i only ever depends on the two totals immediately before it.
This is the same "running pair" DP shape as Climbing Stairs — no full array needed.
Step-by-Step Analysis
Initialize rob1 = 0 (best total two houses back) and rob2 = 0 (best total through the previous house).
For each house value n: compute current = max(n + rob1, rob2) — either rob this house plus the best total from two houses back, or skip it and keep the best total through the previous house.
Shift forward: rob1 becomes the old rob2, rob2 becomes current.
After every house is processed, rob2 holds the answer.
Complexity
Time: O(n) — Space: O(1)
Code
def rob(nums: list[int]) -> int:
rob1, rob2 = 0, 0
for n in nums:
rob1, rob2 = rob2, max(n + rob1, rob2)
return rob2
Code Explanation
How the solution above works, piece by piece.
At each house choose: rob it (add its money to the best total from two houses back, since neighbours can't both be robbed) or skip it (keep the best total from the previous house).
rob1 = best total up to two houses back, rob2 = best total up to the previous house.
rob1, rob2 = rob2, max(n + rob1, rob2) computes the new best and shifts the window in one step.
After the last house, rob2 is the answer.
O(n) time, O(1) space.
Visual Walkthrough
Running it on nums = [1, 2, 3, 1]:
Robbing houses 0 and 2 (1 + 3 = 4) beats every other non-adjacent choice. The running best becomes 1, 2, 4, 4.