Largest Sum of Non-Adjacent Houses

MediumArraysDynamic programming203 tests

Houses stand in one straight row. You get an array money, where money[i] is the amount you can take from house i.

You may choose any set of houses, but you may not choose two houses that are next to each other. House i is next to house i - 1 and house i + 1 only. The first and the last house are at opposite ends of the row, so they are not next to each other (unless the row has just two houses).

Return the largest total of the houses you choose. Choosing no house at all gives a total of 0.

Hint

Go from left to right. For each house, the best total so far is the larger of two choices:

skip this house: the best total up to the house before it, or
take this house: its money plus the best total up to two houses before it.

You only need to keep the last two best totals, so the extra memory is O(1).

Examples

Example 1

Input:: [3,10,4,2,9]
Output:: 19

Choose houses 1 and 4: 10 + 9 = 19. Houses 0, 2 and 4 give only 3 + 4 + 9 = 16.

Example 2

Input:: [8,1,1,8]
Output:: 16

Choose houses 0 and 3: 8 + 8 = 16. You may skip two houses in a row. In a straight row the first and last house are not next to each other.

Example 3

Input:: [4,4,4,4,4]
Output:: 12

Choose houses 0, 2 and 4: 4 + 4 + 4 = 12.

Constraints

1 <= money.length <= 60
0 <= money[i] <= 500

Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.