algorithm - 具有特殊条件的数组中的最大总和

Question

假设我们有一个包含 n 个元素的数组 (n%3 = 0)。在每个步骤中，从数组中取出一个数字。你要么拿最左边的，要么拿最右边的。如果您选择左边的数字，则此元素将添加到总和中，并删除右边的两个数字，反之亦然。

示例:A = [100,4,2,150,1,1]，总和 = 0。

1. 取最左边的元素。 A = [4,2,150] 总和 = 0+100 =100

2.取最右边的元素。 A = [] 总和 = 100+150 = 250

所以 A 的结果应该是 250，序列应该是左，右。

如何计算数组中的最大总和？我怎样才能确定我必须提取元素的顺序？

我想这个问题最好用动态规划来解决，然后通过回溯来确定具体的顺序。

Answer 1

底层问题可以通过动态规划解决，如下所示。状态空间可以定义为

M(i,j) := maximum value attainable by chosing from the subarray of
          A starting at index i and ending at index j
          for any i, j in {1, N} where `N` is the number of elements
          in the input.

其中递归关系如下。

M(i,j) = max { M(i+1, j-2) + A[i], M(i+2, j-1) + A[j] }

这里，第一个值对应于选择添加数组的开头，而第二个值对应于选择减去数组的结尾。基本情况是值 0 的状态，其中 i=j。