最大化最后三个剩余元素的总和

Question

给定一个包含 n 个元素的数组，其中 n 为奇数。在一次操作中，您 可以选择一个索引 i，使得 1 ≤ i < n and remove ai and ai+1 from the array and concatenate the remaining array. You have to keep doing the operation until there are only 3 elements remaining in the array, say x, y and z. The objective is to do the operation in such a way that the sum x+y+z of the remaining 3 elements is maximized. Report the maximum sum you can obtain after doing the operations in any order.

我尝试过暴力破解，但我正在寻找最佳解决方案

Answer 1

首先，删除的顺序没有区别。如果我们删除a_i和a_j，那么先删除a_i还是先删除a_j没有什么区别。 （定理1）

根据定理1，我们可以考虑从数组末尾开始删除。

对于Array[0..n-1]，我们考虑元素Array[n-1]，有两种选择：

1. 通过对数组[n-2]执行删除来删除数组[n-1]
2. 保留数组[n-1]，然后转到数组[n-2]

所以我们定义：

Sol(n, k) is the maximum answer by keeping k numbers in array[0..n]

然后我们有：

Sol(n, k) = max(
  Sol(n - 1, k - 1) + array[n] # keep array[n]
  , Sol(n - 2, k) # delete both array[n] and array[n-1]
)

代码：

ANS_MAX = 10**100


def sol(numbers):
    mem = {}

    def _sol(n, k):
        if mem.get((n, k)) is not None:
            return mem.get((n, k))
        if k == 0:
            return 0
        if n < 0:
            return -ANS_MAX
        ans = max(_sol(n - 2, k), _sol(n - 1, k - 1) + numbers[n])
        mem[(n, k)] = ans
        return ans

    return _sol(len(numbers) - 1, 3)


print(sol([1, 1, 1]))
print(sol([1, 1, 1, 1, 9, -9, 9]))