House robber
At each item, choose to take it (and skip the one before) or leave it — keep whichever choice wins. About 11 minutes.
Adding up became choosing
A street of houses, each with some cash inside. You can take from any houses you like, except two next door to each other: that sets off the alarm. What's the most you can collect?
Until now, every answer was a sum: all the ways in, added together. Here you have a real decision at each house, take it or leave it, and you want the better of the two, not both. That's the new idea in this stage.
House 0: take it. The best so far is 2.
What each choice leaves you with
Stand in front of a house and ask: what's the best I can have by the time I've passed it?
If you skip it, you keep the best you had one house ago. If you take it, you can't have taken the house just before, so you get this house's cash plus the best from two houses ago. Keep whichever is bigger, then walk on. For 2, 7, 9, 3, 1 you end with 12: the first, third and fifth houses.
prev, best = 0, 0
for money in nums:
take = prev + money
prev, best = best, max(best, take)
return bestHouses hold 2, 7, 9 and 3. What's the most you can have after passing the third house (the 9)?
- A11
- B9
- C16
Show the answer
11. Skipping the 9 keeps 7. Taking it gives 9 plus the best two houses back (2): 11. 11 wins.
House robber
nums[i] is the money in house i, in a row of houses. You may rob any houses you like, but never two houses that are next to each other (robbing both would trip an alarm). Return the maximum total money you can rob.
nums = [2, 7, 9, 3, 1] → 12
1 ≤ nums.length ≤ 1,000 · 0 ≤ nums[i] ≤ 1,000