Collect without neighbours
Reported in interviews at (where)
Houses stand in a row and coins[i] is what house i holds. You may take the coins from any houses you like, as long as you never take from two houses that stand next to each other.
Return the most coins you can collect.
- Input
coins = [6,1,2,9,3]- Output
15
Take houses 0 and 3: 6 + 9. Adding house 4 would touch house 3.
- Input
coins = [4,4]- Output
4
The two houses are neighbours, so only one of them.
Limits
1 <= coins.length <= 1000000 <= coins[i] <= 10000
Hints
Hint 1
The best up to house i either skips house i, or takes it and adds the best up to house i - 2.
Where this was reported
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
