A row of houses stands along a street, and nums[i] is the cash inside house i. Neighbouring houses share an alarm: if two houses next to each other are both robbed on the same night, the alarm goes off.
Return the most cash you can take in one night without robbing two adjacent houses.
Rob the first and the last house. Skipping two houses in a row is allowed, and here it beats taking every other house (5 + 1).
Counting from 0, houses 1 and 4 give 9 + 6. Houses 0, 2 and 4 give only 2 + 4 + 6 = 12.
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 400Go from left to right. At each house there are two choices: rob it, so the house before was skipped, or skip it and keep the best total so far.
Stand in front of one house and ask a single question: rob it or not?
Time O(n)Space O(1)
The full walkthrough and code are part of Premium
10