Problem Overview

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The security system is set up such that you cannot rob two adjacent houses without triggering an alarm.

Given an array of non-negative integers representing the amount of money in each house, determine the maximum amount of money you can rob without alerting the police.

This problem tests understanding of:

• Dynamic Programming (optimal substructure, state transitions)

• Space optimization (reducing O(n) to O(1))

• Constraint variations (circular arrays, variable gap constraints)

Part 1: Basic Problem

Given an integer array nums representing the amount of money in each house, return the maximum amount of money you can rob tonight without alerting the police.

Constraint: You cannot rob two adjacent houses.

Example

`

Example 1

nums = [1, 2, 3, 1]

Output: 4

Explanation: Rob houses at indices 0 and 2 (money = 1 and 3).

Total = 1 + 3 = 4

Example 2

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

Output: 12

Explanation: Rob houses at indices 0, 2, and 4 (money = 2, 9, and 1).

Total = 2 + 9 + 1 = 12

Example 3

nums = [5, 3, 4, 11, 2]

Output: 16

Explanation: Rob houses at indices 0 and 3 (money = 5 and 11).

Total = 5 + 11 = 16

`

Requirements

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 400