1. Problem Summary

You are given an array nums where each element represents the amount of money stored in a house along a street.

You must determine the maximum amount of money you can rob, with the restriction that:

• you cannot rob two adjacent houses
• you may rob zero, one, or multiple non-adjacent houses
• the goal is to maximize total stolen amount

Example interpretation:
If you rob house i, you cannot rob houses i-1 or i+1.

---

2. Key Insights

Adjacent constraint makes greedy invalid

You cannot simply take all high values because adjacency restrictions matter.

Dynamic Programming fits perfectly

At each index, there are only two choices:

1. Rob this house (and skip previous)
2. Skip this house (take best up to previous)

Recurrence relation

Let dp[i] be the max money collectable up to house i:

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

Meaning:

• either skip current → keep previous max
• or rob current → add nums[i] to dp two houses back

Base initialization

dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

Space optimization

Since each dp state depends only on previous two, we can reduce to O(1).

---

3. Approach

Dynamic Programming (Iterative)

Steps:

1. If array has only 1 element, return nums[0]
2. Initialize:
   • prev2 = nums[0]
   • prev1 = max(nums[0], nums[1])
3. For each house from index 2 onward: current = max(prev1, prev2 + nums[i])
4. Slide window:
   • prev2 = prev1
   • prev1 = current
5. Return prev1 as final maximum

This guarantees the optimal non-adjacent selection.

---

4. Time and Space Complexity

Time Complexity: O(N)

Each house is processed once.

Space Complexity:

• O(1) using optimized version
• O(N) if dp array is stored

---

5. Java Solution (Optimized DP)

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }

        int prev2 = nums[0];
        int prev1 = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            int current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

---

6. Dry Run Example

Input:

nums = [2, 7, 9, 3, 1]

Step-by-step:

Initialization:

prev2 = 2
prev1 = max(2, 7) = 7

Index 2: num = 9

current = max(7, 2 + 9) = 11
prev2 = 7
prev1 = 11

Index 3: num = 3

current = max(11, 7 + 3) = 11
prev2 = 11
prev1 = 11

Index 4: num = 1

current = max(11, 11 + 1) = 12
prev2 = 11
prev1 = 12

Final result: 12

Meaning best strategy:
Rob houses with values 2, 9, 1 OR 7, 3, 1
Best total = 12

---

Another Dry Run (edge case)

Input:

nums = [1, 2, 3, 1]

Initialization:
prev2 = 1
prev1 = 2

Index 2:
current = max(2, 1+3) = 4
prev2 = 2
prev1 = 4

Index 3:
current = max(4, 2+1) = 4
prev2 = 4
prev1 = 4

Final answer: 4