Introduction

This is the classic "maximum sum of non-adjacent elements" problem. The constraint that you cannot pick neighboring coins means greedy choices are unreliable, so the standard solution is dynamic programming: at each position, decide whether taking the current coin beats skipping it.

Problem Restatement

Given a row of coins, each with a value, choose a subset such that:

• no two chosen coins are adjacent
• the total sum is as large as possible

Example:

[5, 1, 2, 10, 6, 2]

The optimal answer is 17, obtained by choosing 5, 10, and 2.

The crucial detail is that picking a coin blocks only its immediate neighbors, not every later coin.

Why Greedy Fails

A tempting strategy is "always take the larger coin you see." That fails because a locally good choice can block a better combination later.

For example:

[4, 5, 4]

Greedy might pick 5 and stop at total 5, but the optimal choice is 4 + 4 = 8.

That is why the problem needs a recurrence instead of a one-step rule.

Dynamic Programming Recurrence

Let dp[i] mean the best sum we can obtain using coins up to index i.

At each index i, there are only two meaningful options:

1. skip coin i, giving dp[i - 1]
2. take coin i, giving coins[i] + dp[i - 2]

So the recurrence is:

dp[i] = max(dp[i - 1], coins[i] + dp[i - 2])

Base cases:

• 'dp[0] = max(0, coins[0]) if negative values are allowed'
• 'dp[1] = max(dp[0], coins[1])'

If all values are non-negative, the logic is even simpler.

Python Implementation

1def max_non_adjacent_sum(coins):
2    if not coins:
3        return 0
4    if len(coins) == 1:
5        return coins[0]
6
7    dp = [0] * len(coins)
8    dp[0] = coins[0]
9    dp[1] = max(coins[0], coins[1])
10
11    for i in range(2, len(coins)):
12        dp[i] = max(dp[i - 1], coins[i] + dp[i - 2])
13
14    return dp[-1]
15
16print(max_non_adjacent_sum([5, 1, 2, 10, 6, 2]))

This runs in linear time and always produces the optimal answer.

Space Optimization

The full dp array is not necessary if you only want the sum. Each state depends only on the previous two.

1def max_non_adjacent_sum_optimized(coins):
2    include_prev = 0
3    exclude_prev = 0
4
5    for value in coins:
6        new_include = exclude_prev + value
7        new_exclude = max(include_prev, exclude_prev)
8        include_prev = new_include
9        exclude_prev = new_exclude
10
11    return max(include_prev, exclude_prev)
12
13print(max_non_adjacent_sum_optimized([5, 1, 2, 10, 6, 2]))

This version still runs in O(n) time but uses O(1) extra space.

Recovering Which Coins Were Chosen

Sometimes you need the actual set of selected coins, not just the best sum. In that case, keep the dp array and walk backward.

1def chosen_coins(coins):
2    if not coins:
3        return []
4    if len(coins) == 1:
5        return [coins[0]]
6
7    dp = [0] * len(coins)
8    dp[0] = coins[0]
9    dp[1] = max(coins[0], coins[1])
10
11    for i in range(2, len(coins)):
12        dp[i] = max(dp[i - 1], coins[i] + dp[i - 2])
13
14    result = []
15    i = len(coins) - 1
16    while i >= 0:
17        if i == 0:
18            result.append(coins[0])
19            break
20        if dp[i] == dp[i - 1]:
21            i -= 1
22        else:
23            result.append(coins[i])
24            i -= 2
25
26    return list(reversed(result))
27
28print(chosen_coins([5, 1, 2, 10, 6, 2]))

This makes the algorithm more useful in practice because you can explain or verify the chosen subset.

Variations

The same recurrence appears in many disguises:

• house robber problems
• selecting non-overlapping rewards on a line
• maximizing sum with spacing constraints

If the coins are arranged in a circle, the first and last coins become adjacent. Then solve the problem twice:

• once excluding the first coin
• once excluding the last coin

and take the better result.

Common Pitfalls

• Using a greedy strategy based on the biggest nearby coin, which misses better long-range combinations.
• Forgetting the correct recurrence and adding coins[i] to dp[i - 1], which illegally allows adjacent picks.
• Handling the empty list and one-element list as afterthoughts instead of explicit base cases.
• Optimizing to constant space too early when you still need to reconstruct which coins were chosen.
• Missing the circular variant where the first and last coins are also adjacent and therefore cannot both be selected.

Summary

• This is a dynamic programming problem, not a greedy one.
• At each position, compare skipping the coin with taking it plus the best answer two steps back.
• The optimal recurrence is dp[i] = max(dp[i - 1], coins[i] + dp[i - 2]).
• The maximum sum can be computed in linear time and constant extra space.
• If you need the chosen coins themselves, keep the DP states and backtrack.