Facebook采访:通过选择带有数字的方框来查找最大总和的顺序,当它旁边的两个被销毁时

Question

没有找到任何类似的问题.这是最后一轮Facebook问题:

给你一盒盒子.每个盒子上都有一个非负数,可以重复.

编写一个函数/算法,告诉您选择框的顺序,它将为您提供最大总和.

如果您选择一个方框,它就会从环中取出,它旁边的两个方框(在您选择的方框的右侧和左侧)也是如此.

所以,如果我有一个
{10 3 8 12} 的戒指

如果我选择12,8和10将被销毁而你剩下3.

最大值将首先选择8然后选择10,或者先选择10然后选择8.

我尝试通过取自​​己的值重新分配它们的值,然后减去旁边的两个作为成本.

所以老戒指是{10 3 8 12}

新环是{-5,-15,-7,-6},我会选择最高的.

但是,如果你有{10,19,10,0},这肯定不起作用,你应该取两个10,但算法将取19和0.

请帮忙？

它很可能是动态编程,但我不知道如何.

戒指可以是任何尺寸.

Answer 1

这是解决这个问题的一些Python：

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])

输出：

总数：18
选择：10 索引：0 新列表：[8]
选择：8 索引：0 新列表：[]

总数: 20
选择: 10 索引: 0 新列表: [10]
选择: 10 索引: 0 新列表: []

毫无疑问，它可以进行一些优化。关键位是val()，它计算给定环的总价值。剩下的只是簿记。