The problem
Houses along a street hold nums[i] in money. Robbing two neighbouring houses sets off an alarm.
Return the most money you can take without robbing two neighbours.
Examples
01
- Input
nums = [1, 2, 3, 1]
- Output
4
02
- Input
nums = [2, 7, 9, 3, 1]
- Output
12
Constraints
- 1 ≤ nums.length ≤ 100
- 0 ≤ nums[i] ≤ 400
The idea
Let best(i) be the most from houses 0 to i. For house i there are two choices: leave it, and take best(i − 1); or rob it, which rules out house i − 1, and take best(i − 2) + nums[i].
best(i) = max(best(i − 1), best(i − 2) + nums[i]). Walk the street once, keeping the last two values. For [2, 7, 9, 3, 1]: 2, 7, 11, 11, 12.
- Time
- O(n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def rob(self, nums: List[int]) -> int: # best(i): the most from houses 0..i. Either skip house i, or rob it and skip i - 1. # best(i) = max(best(i - 1), best(i - 2) + nums[i]) prev2 = prev1 = 0 for x in nums: prev2, prev1 = prev1, max(prev1, prev2 + x) return prev1