# House Robber

**1. Clarify the problem:**
Before diving into solving the problem, let's clarify the requirements:

- We are given an array
`nums`

of non-negative integers representing the amount of money in each house. - We want to maximize the amount of money we can rob without robbing adjacent houses.
- The goal is to determine the maximum amount of money that can be robbed.

**2. Analyze the problem:**
To solve this problem, we can use dynamic programming. We need to find the maximum amount of money that can be robbed without robbing adjacent houses.

**3. Design an algorithm:**
Here is the algorithm to find the maximum amount of money that can be robbed:

- If the input array
`nums`

is empty, return 0. - If the input array
`nums`

has only one house, return the money in that house. - Initialize two variables:
`prev1`

and`prev2`

to store the maximum amount of money that can be robbed from the previous two adjacent houses. - Iterate through the array
`nums`

starting from the third house (index 2) up to the last house (index n-1).- Calculate the maximum amount of money that can be robbed from the current house by adding the current house's money to the maximum amount that can be robbed from the previous non-adjacent house (i.e.,
`prev2`

). - Update
`prev1`

to store the maximum amount that can be robbed from the previous house (i.e.,`prev1`

becomes the previous non-adjacent house for the next iteration). - Update
`prev2`

to store the maximum amount that can be robbed from the current house (i.e.,`prev2`

becomes the maximum amount that can be robbed from the previous house for the next iteration).

- Calculate the maximum amount of money that can be robbed from the current house by adding the current house's money to the maximum amount that can be robbed from the previous non-adjacent house (i.e.,
- Return the maximum amount of money that can be robbed, which is the maximum value between
`prev1`

and`prev2`

.

**4. Explain your approach:**
The approach involves using dynamic programming to iteratively calculate the maximum amount of money that can be robbed without robbing adjacent houses. We keep track of the maximum amounts that can be robbed from the previous two adjacent houses (`prev1`

and `prev2`

). At each iteration, we calculate the maximum amount that can be robbed from the current house by adding the current house's money to the maximum amount that can be robbed from the previous non-adjacent house (`prev2`

). We update `prev1`

and `prev2`

accordingly and continue the iteration until we reach the last house. Finally, we return the maximum amount of money that can be robbed, which is the maximum value between `prev1`

and `prev2`

.

**5. Write clean and readable code:**

python

```
def rob(nums):
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
prev1 = nums[0]
prev2 = max(nums[0], nums[1])
for i in range(2, n):
curr = max(prev1 + nums[i], prev2)
prev1, prev2 = prev2, curr
return max(prev1, prev2)
```

**6. Test your code:**

python

```
# Test case 1
nums1 = [1, 2, 3, 1]
print(rob(nums1)) # Output: 4
# Test case 2
nums2 = [2, 7, 9, 3, 1]
print(rob(nums2)) # Output: 12
# Test case 3
nums3 = [2, 1, 1, 2]
print(rob(nums3)) # Output: 4
```

**7. Optimize if necessary:**
The provided solution already has an optimal time complexity of O(n), where n is the length of the input array `nums`

. We only iterate through the array once, updating the maximum amounts that can be robbed from the previous two adjacent houses. There is no need for further optimization.

**8. Handle error cases:**
The code assumes that the input array `nums`

contains non-negative integers. It does not handle invalid input or error cases explicitly. If the input array contains negative integers, the behavior of the code may be unpredictable.

**9. Discuss complexity analysis:**
The time complexity of the solution is O(n), where n is the length of the input array `nums`

. This is because we iterate through the array once. The space complexity is O(1) as we only use a constant amount of additional space to store the variables `prev1`

, `prev2`

, and `curr`

.