具有特殊条件的阵列中的最大总和

Question

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

示例:A = [100,4,2,150,1,1],sum = 0.

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

2.采取最右边的元素.A = [] sum = 100 + 150 = 250

所以A的结果应该是250,序列是Left,Right.

如何计算数组中可以得到的最大总和？我如何确定我必须提取元素的顺序？

我想这个问题最好用动态编程来解决,然后可以通过回溯来确定具体的顺序.

Answer 1

潜在的问题可以通过动态编程解决如下.可以通过letting来定义状态空间

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.