Coin-row problem

A set of n coins is placed in a row. The coins have positive values which need not be distinct. Find the maximum amount that can be collected given the constraint that no two adjacent coins can be picked up.

Consider n coins with values {v1, v2, v3, …, vn} and let amount(i) represent the maximum amount that can be collected after 'i' coins. As we see each coin, we will have to decide if the coin has to be picked up or not. To make this decision, two cases have to be considered –

If we pick the i'th coin, we cannot pick the (i - 1)th coin, The payoff is amount(i -2) + v(i) or

we skip the current coin and the payoff is the amount(i - 1)

This can be stated with the recursive relation

Amount(n) = max{ v(n) + Amount(n-2), Amount(n-1) } and Amount (1) = v(1)

For example, consider the coins set with values {5, 1, 2, 10, 5, 2}. Here is the step-by-step manner to fill the amount array.

Step 1: Initialize amount(0) = 0 and amount(1) = coins(1)

coins	-	5	1	2	10	5	2
amount	0	5

Step 2: amount(2) = max{ coins(2) + amount(0), amount(1) }

                             = max{ 1+0, 5} = 5

coins	-	5	1	2	10	5	2
amount	0	5	5

Step 3: amount(3) = max{ coins(3) + amount(1), amount(2) }

                             = max{ 2+5, 5} = 7

coins	-	5	1	2	10	5	2
amount	0	5	5	7

Step 4: amount(4) = max{ coins(4) + amount(2), amount(3) }

                             = max{ 10+5, 7} = 15

coins	-	5	1	2	10	5	2
amount	0	5	5	7	15

Step 5: amount(5) = max{ coins(5) + amount(3), amount(4) }

                             = max{ 5+7, 15} = 15 

coins	-	5	1	2	10	5	2
amount	0	5	5	7	15	15

Step 5: amount(6) = max{ coins(6) + amount(4), amount(5) }

                             = max{ 2+15, 15} = 17

coins	-	5	1	2	10	5	2
amount	0	5	5	7	15	15	17

The value at amount(6) represents the maximum possible amount that can be collected by considering a set of 6 coins placed in a row with the given constraint.

Here is the C++ code. A '0' is inserted as the first entry in the coins array to enhance readability.

int coins[7] = {0, 5, 1, 2, 10, 5, 2};

int amount[7];

void MaxAmount(int* amount, const int* coins) {

  amount[0] = 0;

  amount[1] = coins[1];

  for(int i = 2; i < 7; ++i) {

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

  }

  cout << amount[6] << endl;

}

We can compute the amount array by checking all the coins exactly once. This dynamic programming approach has a time complexity of O(n) and takes an additional array space of O(n).