House Robber

Problem

You are given a list of non-negative integers nums, where nums[i] is the amount of value stored at position i along a street. You may collect from any subset of positions, with one restriction: you can never collect from two positions that are directly next to each other. Return the largest total you can collect.

• The list has between 1 and 5,000 positions.
• Each value is a non-negative integer no larger than 10,000.

Examples

• nums = [3, 10, 4, 6, 8] → 18. Take positions 1 and 4 (10 + 8). Taking 10 and 4 together is not allowed because they are adjacent.
• nums = [6, 1, 1, 6] → 12. Take both ends; the two 1s in the middle are never worth displacing a 6.
• nums = [9] → 9. A single position can always be taken.

Hints

1. Consider the last position. Either you take it or you skip it. What does each choice force on the rest of the list?
2. If you knew the best total achievable using only the first i-1 positions and only the first i-2 positions, could you decide position i without looking further back?
3. This is a 1D DP with the recurrence best[i] = max(best[i-1], best[i-2] + nums[i]), and it needs only two rolling values.