House Robber
The problem
Each house along a street contains a nonnegative amount. Find the maximum total obtainable without choosing two neighboring houses. Choosing none is allowed.
Example
[3, 8, 4, 5] → 13 by choosing 8 and 5
Need a hint?
At each house, choose between skipping it and combining it with the best earlier non-neighboring total.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Track the best total through the previous house and through the house before that. For value x, compute max(previous, beforePrevious + x), then shift the two states. Initialize both to zero.
Complexity
O(n) time and O(1) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.