#198 House Robber
A row of houses each holds a stash of cash, given as an array nums where
nums[i] is the amount in house i. You may rob any subset of houses, with
one rule: never rob two adjacent houses (linked alarms).
Return the maximum total you can collect.
Examples
Input
nums = [1, 2, 3, 1]Output
4Rob houses 0 and 2: 1 + 3 = 4. Robbing 1 and 3 gives only 3.
Input
nums = [2, 7, 9, 3, 1]Output
12Rob houses 0, 2, and 4: 2 + 9 + 1 = 12.
Constraints
1 ≤ nums.length ≤ 1000 ≤ nums[i] ≤ 400
The explainer is the good part.
Sign in for the full intuition build-up, every approach from naive to optimal with complexity analysis, progressive hints, and commented solutions in Python, JavaScript, and Java. All free.
Want a taste first? Try a free sample: Two Sum or Valid Parentheses.