House Robber

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you from robbing all of them is that adjacent houses have security systems connected: if two adjacent houses are broken into on the same night, the police will be contacted.

Given an integer array nums where nums[i] represents the amount of money in the ith house, return the maximum amount of money you can rob tonight without alerting the police (i.e., without robbing two adjacent houses).

Examples

Example 1:

Input: nums = [1, 2, 3, 1]
Output: 4
Explanation: Rob house 0 (money = 1) and house 2 (money = 3).
  Total = 1 + 3 = 4.

Example 2:

Input: nums = [2, 7, 9, 3, 1]
Output: 12
Explanation: Rob house 0 (money = 2), house 2 (money = 9), and house 4 (money = 1).
  Total = 2 + 9 + 1 = 12.

Example 3:

Input: nums = [2, 1, 1, 2]
Output: 4
Explanation: Rob house 0 (money = 2) and house 3 (money = 2).
  Total = 2 + 2 = 4.

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

Expected Complexity

• Time: O(n). single pass through the array
• Space: O(1). only two variables needed (optimized from O(n) DP table)