703. Quiet Burglar
A night-time collector walks down a street of n houses in order. The collector may take the loot houses[i] from house i, but every house has a motion light that is linked to its two neighbours: taking from two neighbouring houses on the same night trips the alarm, so no two chosen houses may be next to each other.
Return the largest total loot that can be collected without ever choosing two adjacent houses. Choosing nothing is allowed, and the answer is 0 when every house is worth 0.
Aim for time O(n) and extra space O(1).
Example 1
- Input:
- houses = [6,1,9,4,8]
- Output:
- 23
- Explanation:
Take houses 0, 2 and 4 for 6 + 9 + 8 = 23; no other non-adjacent choice beats it.
Example 2
- Input:
- houses = [3,10,2,2,9,1]
- Output:
- 19
- Explanation:
Take houses 1 and 4 for 10 + 9 = 19, which beats 3 + 2 + 9 = 14 and 10 + 2 + 1 = 13.
Constraints
1 ≤ n = houses.length ≤ 105
0 ≤ houses[i] ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)