algorithm - 查找数组中 "accessible"数字的最大乘积和的动态算法

Question

我被要求提供一个动态算法，该算法将采用一系列偶数的数字(包括正数和负数)并执行以下操作:

每“转”两个数字被选择相乘。该算法只能访问序列的任一端。但是，如果选择的第一个数字是最左边的数字，则第二个数字可以是最右边的数字，也可以是新的最左边的数字(因为旧的最左边的数字已经被“删除/选择”)，反之亦然。该程序的目标是找到每轮选择的两个数字的乘积的最大总和。

示例:

Sequence: { 10, 4, 20, -5, 0, 7 }

Optimal result: 7*10 + 0*-5 + 4*20 = 150

我的进步:

我一直在尝试找到一种动态方法，但运气不佳。我已经能够推断出该程序每次基本上只允许将结束数字乘以“相邻”数字，并且目标是将最小的可能数字乘以最小的可能数字(导致 double负乘法 - 正数，或可达到的最小数)，并在每次结束时继续应用此规则。相比之下，这条规则也适用于相反的方向——每次将最大可能的数字乘以最大可能的数字。也许最好的方法是同时应用这两种方法？我不确定，正如我所提到的，我没有运气为这个问题实现算法。

Answer 1

让我们看看递归和自下而上的制表方法。首先是递归:

{10, 4,20,-5, 0, 7}

First call:

  f(0,5) = max(f(0,3)+0*7, f(2,5)+10*4, f(1,4)+10*7)

Let's follow one thread:

  f(1,4) = max(f(1,2)+(-5)*0, f(3,4)+4*20, f(2,3)+4*0)

f(1,2)、f(3,4) 和 f(2,3) 是“基本情况”并有一个直接的解决方案。该函数现在可以将这些保存在由 i,j 索引的表中，供递归的其他线程稍后访问。例如，f(2,5) = max(f(2,3)+0*7... 还需要 f(2,3) 的值如果该值已经在表中，则可以避免创建另一个函数调用。随着递归函数调用的返回，该函数可以将下一个值保存在表中 f(1,4)，f(2,5) 和 f(0,3)。由于此示例中的数组很短，因此函数调用的减少并不显着，但对于更长的时间数组，重叠函数调用(对相同的 i,j)的数量可能会大得多，这就是为什么内存可以证明更有效的原因。

表格方法是我在其他答案中尝试展开的方法。在这里，我们依靠(在这种情况下)类似的数学公式来计算表中的下一个值，而不是递归，依赖于表中已经计算出的其他值。数组下方的星号旨在说明我们计算值的顺序(使用两个嵌套的 for 循环)。您可以看到，为每个 (i,j) 大小的子集计算公式所需的值要么是基本情况，要么存在于循环顺序的较早位置；它们是:一个子集向左扩展两个元素，一个子集向右扩展两个元素，一个子集向每一侧扩展一个元素。