House Robber

Medium · 1-D Dynamic Programming

You are given an array of integers representing the amount of cash stored in each house along a street. You want to steal as much money as possible tonight, but any two houses that are directly next to each other cannot both be robbed, because their alarm systems are linked. Return the maximum total amount of money you can steal without robbing two adjacent houses.

Examples

Input:  nums = [1,2,3,1]
Output: 4
Why:    Rob house 1 (1) and house 3 (3) for a total of 4, which beats any other combination.

Input:  nums = [2,7,9,3,1]
Output: 12
Why:    Rob houses 1, 3 and 5 (2+9+1=12), which is better than robbing house 2 and 4 (7+3=10).

Input:  nums = [5]
Output: 5
Why:    There is only one house, so just take its money.

Constraints

1 <= nums.length <= 10^4, 0 <= nums[i] <= 1000

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise House Robber

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of House Robber. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.