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

Question

有人要求我提供一个动态算法，该算法将采用一系列偶数的数字（正数和负数）并执行以下操作：

每个 "turn" 两个数字被选择相乘。该算法只能访问序列的任一端。但是，如果选择的 first 号码是最左边的号码，则 second 号码可以是最右边的号码，也可以是新的最左边的号码（因为旧的最左边的数字已经是 "removed/chosen")，反之亦然。程序的objective是求每轮选出的两个数的乘积的最大总和

示例：

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

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

我的进度：

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

Answer 1

您可能正在寻找 动态规划 算法。令 A 为数字数组，此问题的重现将是

f(start,stop) = max( // last two numbers multiplied + the rest of sequence,
                     // first two numbers multiplied + the rest of sequence,
                     // first number*last number + rest of sequence  )

f(start,stop) then 是从 start,stop 开始的数组子序列的最优结果。您应该使用动态编程或记忆来计算所有有效值的 f(start,stop)。

提示：第一部分 // last two numbers multiplied + the rest of sequence 看起来像：

 f(start,stop-2) + A[stop-1]*A[stop-2]

Answer 2

让i和j代表数组的第一个和最后一个索引，A，在上一轮之后。显然，它们必须代表 A 的一些偶数大小的连续子集。那么 dp[i][j] 的一般情况应该是 max(left, right, both) 其中 left = A[i-2]*A[i-1] + dp[i-2][j]、right = A[j+1]*A[j+2] + dp[i][j+2] 和 both = A[i-1]*A[j+1] + dp[i-1][j+1]；对于除最后一个 i 之外的所有 max(A[i]*A[i+1] + dp[i][i+1])，解决方案都是 max(A[i]*A[i+1] + dp[i][i+1])。

幸运的是，我们可以按降序计算 dp，以便始终代表较大的周围子集的所需值已经计算出来（星号代表计算出的子集）：

{10, 4,20,-5, 0, 7}
  *  *  *  *  *  *
  *  *  *  *
  *  *
     *  *  *  *    (70)
     *  *
        *  *  *  *
        *  *
           *  *    left = (80 + 70)
              *  *

Answer 3

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

{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)是"base cases"，有直接解。该函数现在可以将这些保存在由 i,j 索引的 table 中，以供递归的其他线程稍后访问。例如，f(2,5) = max(f(2,3)+0*7... 还需要 f(2,3) 的值，如果该值已经在 table 中，则可以避免创建另一个函数调用。当返回递归函数调用时，函数可以将 f(1,4)、f(2,5) 和 f(0,3) 的下一个值保存在 table 中。由于这个例子中的数组很短，函数调用的减少并不明显，但是对于更长的数组，重叠函数调用的数量（对相同的i,j）可能会大得多，这就是为什么记忆可以证明效率更高。

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

Answer 4

下面是递归方法的代码片段。

  public class TestClass {

  public static void main(String[] args) {
    int[] arr = {10, 4, 20, -5, 0, 7};
    System.out.println(findMaximumSum(arr, 0, arr.length - 1));
  }

  private static int findMaximumSum(int[] arr, int start, int end) {
    if (end - start == 1)
        return arr[start] * arr[end];

    return findMaximum(
        findMaximumSum(arr, start + 2, end) + (arr[start] * arr[start + 1]), 
        findMaximumSum(arr, start + 1, end - 1) + (arr[start] * arr[end]),
        findMaximumSum(arr, start, end - 2)+ (arr[end] * arr[end - 1])
        );
  }

  private static int findMaximum(int x, int y, int z) {
    return Math.max(Math.max(x, y), z);
  }
}

结果为10*4 + 20*7 + -5*0 = 180

同样对于输入 {3,9,7,1,8,2} 答案是 3*2 + 9*8 + 7*1 = 85

Answer 5

让我们把它变成一个甜蜜的动态规划公式。

我们定义子问题如下：

我们想最大化总和，同时选择子数组 i、j 的前两个、第一个和最后一个或最后两个值。

那么递归等式如下所示：

set OPT(i,j) =
    if i == j
        v[i]
    else if i < j:
        max (
            v[i] + v[i+1] + OPT(i + 2,j),
            v[i] + v[j]   + OPT(i + 1,j + 1),
            v[j] + v[j-1] + OPT(i, j - 2)
        )
    else:
        0

拓扑阶：i和j之一或两者都变小。

现在 base case 当 i 等于 j 时，返回值。

然后来到原始问题，调用 OPT(0,n-1) returns 最大和。

时间复杂度是O(n^2)。由于我们使用动态规划，它使我们能够缓存所有值。每个子问题调用，我们最多使用 O(n) 次，并且我们这样做 O(n) 次。

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

Dynamic algorithm to find maximum sum of products of "accessible" numbers in an array

algorithm

recursion

numbers

dynamic

divide-and-conquer