The best you can take without touching neighbours

Each number is the amount in one house, and the houses stand in a row. You may not take from two houses next to each other. Return the most you can take in total.

Worked example#

For [2, 7, 9, 3, 1], at each house you have exactly two choices: take it and add whatever was best two houses back, or skip it and keep whatever was best one house back.

The answer is 12: houses 0, 2 and 4, which is 2 + 9 + 1.

Notice house 1 holds 7, the second largest amount, and the best answer skips it. Taking the largest available each time is exactly the greedy instinct, and here it is wrong.

Why greedy fails and this does not#

The instinct is to keep taking the largest house still available. On the example above that happens to give 12, the right answer, which is exactly how a wrong method survives a first test.

Try [4, 5, 4]. Greedy takes the 5, which rules out both 4s, and ends with 5. The answer is 8: take both 4s and skip the largest house entirely.

Taking one house changes which houses remain, so a choice that looks best now can cost more later. That is the signal that greedy does not apply, and the reason to compute every position instead of guessing.

What makes this solvable is that the best answer up to a house depends only on the best answers at the two houses before it. So compute them in order and each one is a single comparison.

Only two numbers needed#

The table above has one row per house, but each row reads only the two before it. So you never need the whole table: two running values are enough.

twoBack = 0
oneBack = 0
for each amount:
    best = max(amount + twoBack, oneBack)
    twoBack = oneBack
    oneBack = best

That takes the memory from O(n) to O(1), and it is the standard next step once a table's rows only look a fixed distance back.

The cost#

Time O(n), one pass. Memory O(1).

Constraints#

• 1 <= n <= 100000
• 0 <= nums[i] <= 10000