Medium

Quiz

#198 House Robber

APPROACH

You are a thief planning to rob houses along a street. Each house stores some cash. Adjacent houses share an alarm that triggers if two neighboring houses are robbed on the same night.

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

Example 1:

Input: nums = [1,2,3,1]

Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).

Total amount you can rob = 1 + 3 = 4.

Example 2:

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

Output: 12

Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).

Total amount you can rob = 2 + 9 + 1 = 12.

1 of 4

1:00

What is the optimal approach for this problem?