House Robber

You are given an integer array nums where nums[i] represents the amount of money the ith house has. The houses are arranged in a straight line, i.e. the ith house is the neighbor of the (i-1)th and (i+1)th house.

You are planning to rob money from the houses, but you cannot rob two adjacent houses because the security system will automatically alert the police if two adjacent houses were both broken into.

Return the maximum amount of money you can rob without alerting the police.

nums[0] + nums[2] = 1 + 3 = 4.

nums[0] + nums[2] + nums[4] = 2 + 8 + 6 = 16.

Approach

Use dynamic programming with two variables: prev1 is the best up to the previous house, prev2 is the best up to the house before that. For each house, decide to rob it (prev2 + num) or skip it (prev1).

Why It Works

At each house, the optimal decision depends only on the best totals of the two previous positions. This matches the recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]), which guarantees optimality.

Complexity

• Time: O(n)
• Space: O(1)

Reference Implementation (Python)

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev2 = 0
        prev1 = 0
        for num in nums:
            prev2, prev1 = prev1, max(prev1, prev2 + num)
        return prev1