Coins of different denominations are placed one after the other, pick coins to maximize the sum

Question

Coins of different denominations are placed one after the other. You need to pick coins one by one (except first and last) until there are only 2 coins (first and the last) left. Each time you pick a coin you multiply it's left and right coins values. The problem is to pick coins in such an order so that the sum of all the multiplications is maximum. For example:

let say coins are placed as 1, 6, 7, 4

There are 2 ways to pick coins:

First way: first pick 6, this will result in 1*7 = 7 and then pick 7, this will result in 1*4 = 4, so total would be 7 + 4 = 11

Second way: first pick 7, this will result in 6*4 = 24 and then pick 6, this will result in 1*4 = 4, so total would be 24 + 4 = 28

As 28 is largest, that's our answer.

I could find the right answer by recursively traversing through all the possible cases and comparing their output values but this solution is very inefficient as it takes exponential time. Please let know how can this problem be solved more efficiently.

EDIT : The recursive solution

int remove (int a [], int end, int pos) {
    int tmp = a[pos];
    for (int i = pos + 1; i <= end; i++) {
        a[i - 1] = a[i];
    } a[end] = 0;
    return tmp;
}

int * insert (int a [], int end, int pos, int val) {
    for (int i = end; i >= pos; i--) {
        a[i + 1] = a[i];
    } a[pos] =  val;
    return a;
}

/*  a: input array, {1, 7, 6, 4}
    end: array last index, 3 for above case
*/
int getMaxSum (int a [], int end, int sum = 0) {
    if (end == 1) {
        return sum;
    }

    int maxSum = 0;

    for (int i = 1; i < end; i++) {
        auto mult = a[i - 1]*a[i + 1];
        auto val = remove(a, end, i);
        auto tmp = getMaxSum (a, end - 1, sum + mult);
        if (tmp > maxSum)
            maxSum = tmp;
        insert(a, end - 1, i, val);
    }

    return maxSum;
}

Answer 1

This can be solved using modified Matrix Chain Multiplication problem using Dynamic programming.

Suppose given numbers are A, B, C, D

A B C D
1 6 7 4

Now convert these number to:

• matrix M1 of dimensions AxB
• matrix M2 of dimensions BxC

• matrix M3 of dimensions CxD

  M1 M2 M3
  AB BC CD
  16 67 74
  

Normally, if 2 compatible matrices of dimension AB and BC are multiplied then cost of multiplication is AB x BC = ABC. ABC is product of 3 elements A, B & C.

In this modified algorithm, the cost will be AxC (since picking element [i] will result in cost [i-1]x[i+1]).

That is, AB x BC = AC. AC is product of 2 elements A & C.

Now, try to parenthesize the matrices M1, M2 and M3 in all the possible ways such that the cost is maximum.

Possible parentheses:

[1] (M1 (M2 M3))
[2] ((M1 M2) M3) 


[1] 
{AB x (BCxCD)} => {AB x BD}
{(AB) x (6 x 4 = 24)} => {1 x 4 = 4}  ,  so 24 + 4 = 28
Elements picking order {C} -> {B}

[2]
{(AB x BC) x CD} => {AC x CD}
{(1 x 7 = 7) x CD} => {1 x 4 = 4} , so 7 + 4 = 11
Elements picking order {B} -> {C}

So, using [1], the cost is max, i.e. 28, and elements should be picked in following order: C -> B.