156. House Robber

At each house you either skip it (keep the best total up to the previous house) or rob it (its money plus the best total up to two houses back). dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

Idea

Standing at house i, you face a binary choice:

• Skip house i: your best is whatever you had through house i-1 → dp[i-1].
• Rob house i: you can't have robbed i-1, so add its money to your best through house i-2 → dp[i-2] + nums[i].

Take the better of the two:

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

Only the last two values matter, so we track them in two rolling variables and use O(1) space.

Algorithm

1. prev = 0 (best two houses back), curr = 0 (best one house back).
2. For each x in nums: prev, curr = curr, max(curr, prev + x).
3. Return curr.

Worked example: [2,7,9,3,1]

Maximum = 12 (rob houses 0, 2, 4: 2 + 9 + 1).

Complexity

• Time: O(n).
• Space: O(1) with rolling variables.

class Solution {
    public int rob(int[] nums) {
        int prev = 0, curr = 0;
        for (int x : nums) {
            int next = Math.max(curr, prev + x);
            prev = curr;
            curr = next;
        }
        return curr;
    }
}