Facebook interview: find out the order that gives max sum by selecting boxes with number in a ring, when the two next to it is destroyed

Question

Didn't find any similar question about this. This is a final round Facebook question:

You are given a ring of boxes. Each box has a non-negative number on it, can be duplicate.

Write a function/algorithm that will tell you the order at which you select the boxes, that will give you the max sum.

The catch is, if you select a box, it is taken off the ring, and so are the two boxes next to it (to the right and the left of the one you selected).

so if I have a ring of
{10 3 8 12}

If I select 12, 8 and 10 will be destroyed and you are left with 3.

The max will be selecting 8 first then 10, or 10 first then 8.

I tried re-assign the boxes their value by take its own value and then subtracts the two next to is as the cost.

So the old ring is {10 3 8 12}

the new ring is {-5, -15, -7, -6}, and I will pick the highest.

However, this definitely doesn't work if you have { 10, 19, 10, 0}, you should take the two 10s, but the algorithm will take the 19 and 0.

Help please?

It is most likely dynamic programming, but I don't know how.

The ring can be any size.

Answer 1

Here's some python that solves the problem:

def sublist(i,l):
    if i == 0:
        return l[2:-1]
    elif i == len(l)-1:
        return l[1:-2]
    else:
        return l[0:i-1] + l[i+2:]

def val(l):
    if len(l) <= 3:
        return max(l)
    else:
        return max([v+val(m) for v,m in [(l[u],sublist(u,l)) for u in range(len(l))]])

def print_indices(l):
    print("Total:",val(l))
    while l:
        vals = [v+val(m) for v,m in [(l[u],sublist(u,l)) for u in range(len(l)) if sublist(u,l)]]
        if vals:
            i = vals.index(max(vals))
        else:
            i = l.index(max(l))
        print('choice:',l[i],'index:',i,'new list:',sublist(i,l))
        l = sublist(i,l)

print_indices([10,3,8,12])
print_indices([10,19,10,0])

Output:

Total: 18
choice: 10 index: 0 new list: [8]
choice: 8 index: 0 new list: []

Total: 20
choice: 10 index: 0 new list: [10]
choice: 10 index: 0 new list: []

No doubt it could be optimized a bit. The key bit is val(), which calculates the total value of a given ring. The rest is just bookkeeping.