Each house on a street has some money stashed in it, given by nums. You may take the money from any set of houses, as long as you never take from two houses that are next to each other.
Return the largest total you can collect.
Examples
Example 1
- Input
- nums = [1, 2, 3, 1]
- Output
- 4
- Why
- Take houses 0 and 2: 1 + 3 = 4.
Example 2
- Input
- nums = [2, 7, 9, 3, 1]
- Output
- 12
- Why
- Take houses 0, 2 and 4: 2 + 9 + 1 = 12.
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 400