House Robber

Intuition

For each house you face a binary decision: skip it and keep whatever was optimal through the previous house, or rob it and add its money to the best total that ended at least two houses back. Encoding this gives dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Because dp[i] only ever looks one and two positions behind, the full array is unnecessary. We keep prev1 for dp[i-1] and prev2 for dp[i-2] and slide them forward as we scan. Starting both at zero cleanly handles the leading houses. The final value of prev1 is the answer.

Algorithm walkthrough

1. 1Initialize prev2 = 0 (best total two houses back) and prev1 = 0 (best total one house back).
2. 2Scan each house value num from left to right.
3. 3Compute curr = max(prev1, prev2 + num): either skip this house or rob it plus the best from two back.
4. 4Slide the window: set prev2 = prev1, then prev1 = curr.
5. 5Continue until every house has been processed.
6. 6Return prev1, which now holds the maximum loot across the whole street.

Implementation

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev2, prev1 = 0, 0
        for num in nums:
            curr = max(prev1, prev2 + num)
            prev2 = prev1
            prev1 = curr
        return prev1