在每个步骤中选择一个加数，然后删除最后一个和第一个元素时的最大和

Question

我有一个数组。每次迭代，我都会从数组中取出一个元素并将其添加到运行总和中。然后，第一个和最后一个元素被丢弃。我不能在同一个初始索引中选择一个元素两次。
我如何找到最大总和？

示例测试用例
[4, 4, 8, 5, 3, 2] ans = 17，选择索引 0，然后选择索引 3，然后选择索引 2。
[1, 5, 5, 2] ans = 10，选择索引 1，然后选择索引 2

我的解决方案是 dp with memoization，但我达到了最大递归深度。

如何在不达到最大递归深度的情况下找到结果？
也许还有另一种方法吗？

Answer 1

假设您正在使用 N 元素数组玩这个游戏。 在第一回合，你有 2 个选择：

1. 从头或尾挑选最大的元素，然后与其他N-2个元素玩同样的游戏；
2. 永远忘记开始和结束，从 N-2 内部选择一个元素。 这就像进入 N-2 游戏，一开始就有一个额外的选择。

为了做出这个选择，你需要知道选择 2 会得到哪个元素。为了弄清楚这一点，你需要考虑 N-2 游戏的 2 种情况 - 要么你在开始时得到一个额外的选择，或者你不这样做。 对于 N-4 游戏，您可能会获得 2 个额外选择，等等。

为了涵盖所有情况，我们可以从中间元素游戏开始，然后向外扩展，计算所有情况下的最佳总和列表——0个额外猜测，1个额外猜测，等等，最多为大小/2个额外猜测.

如果您有大小为 n-2 的列表，则很容易计算大小为 n 的列表。 k 个额外猜测的最佳结果是以下最大值：

1. 开始或结束时最大的元素，加上k个猜测玩n-2的结果；
2. 用k+1次额外猜测进行n-2次的结果；和
3. 如果 k>=1，则为 start end end 元素的总和，加上用 k-1 个猜测进行 n-2 次游戏的结果。

这导致了一个简单的 O(N²) 算法：

def sumgame(ar):
    start = len(ar)//2
    end = len(ar)-start
    if start == end:
        # even number of elements in array
        results = [0]
    else:
        # odd number of elements in array, middle has 1
        results = [ar[start]]

    while start > 0:
        start-=1
        end+=1
        first = ar[start]
        last = ar[end-1]

        # calc result for k=0
        best = max(first, last) + results[0]
        if len(results) > 1:
            best = max(best, results[1])
        newresults = [best]

        # calc rest
        for k in range(1, len(results)+1):
            best = first + last + results[k-1]
            if k < len(results):
                best = max(best, max(first, last) + results[k])
            if k+1 < len(results):
                best = max(best, results[k+1])
            newresults.append(best)
        results = newresults
    
    return results[0]

Answer 2

向后播放，即从内到外。始终将两个新元素添加到最大堆，然后将堆中的最大值移动到总和。

from heapq import *

def sumgame_mine(ar):
    heap = []
    n = len(ar)
    sum = 0
    for i in range(n//2, n):
        for j in {i, n-1-i}:
            heappush(heap, -ar[j])
        sum -= heappop(heap)
    return sum

（Python 只有最小堆，所以我否定这些值。）

使用 Matt （他的“向外扩展”启发了我）和 1000 个从 0 到 999 的随机数数组进行测试，两种解决方案计算出相同的总和：

381147 283.0 ms  sumgame_Matt
381147   1.4 ms  sumgame_mine

测试代码（在线尝试！）：

import random
from time import time

ar = random.choices(range(1000), k=1000)
for f in sumgame_Matt, sumgame_mine:
    t = time()
    print(f(ar[:]), f'{(time()-t)*1e3:5.1f} ms ', f.__name__)

我的解决方案的一个变体，将chosen元素的总和作为all元素减去unchosen元素的总和：

def sumgame_mine(ar):
    heap = []
    n = len(ar)
    for i in range(n//2, n):
        for j in {i, n-1-i}:
            heappush(heap, -ar[j])
        heappop(heap)
    return sum(ar + heap)

在线尝试！

Answer 3

import heapq

def maximize_sum_with_heap(arr):
    left, right = 0, len(arr) - 1
    iteration_counter = 1
    max_heap = []
    total_sum = 0
    
    while left <= right:
        if left <= right:
            heapq.heappush(max_heap, arr[left])
        if left < right:
            heapq.heappush(max_heap, arr[right])
        
        
        while len(max_heap) > iteration_counter:
            heapq.heappop(max_heap)
        
       
        left += 1
        right -= 1
        iteration_counter += 1
    
    return sum(max_heap)