Maximum sum of non-adjacent houses
Each house holds some money in nums. You cannot take from two adjacent houses. Return the maximum total you can take.
Examples: nums=[1,2,3,1] → 4 (houses 1 and 3); nums=[2,7,9,3,1] → 12 (houses 1, 3, 5). Aim for O(n) time and O(1) extra space.
def rob(nums: list[int]) -> int:
# your code hereWrite the implementation.
Dynamic programming with two rolling values. For each house, the best total up to it is max(skip_this = best_without_prev, take_this = best_before_prev + nums[i]). Track two rolling values and update them per house; the answer is the final running best. O(n) time, O(1) space.
- ✗Assuming even-indexed houses are always optimal
- ✗Greedily taking the largest values regardless of structure
- ✗Forgetting the take-vs-skip choice at each house
- →How does the recurrence change if houses form a circle?
- →Why is the greedy largest-first approach wrong here?
At each house you either skip it (keep the best total through the previous house) or take it (the best total two houses back, plus this house's money). Two rolling scalars suffice.
def rob(nums: list[int]) -> int:
prev = prev2 = 0 # best through last house, best through the one before
for x in nums:
prev, prev2 = max(prev, prev2 + x), prev
return prev[1,2,3,1] → take 1 and 3 → 4. [2,7,9,3,1] → take 2, 9, 1 → 12. Each house is visited once with constant extra state, so the solution is O(n) time and O(1) space.
