arrays - 如何在这个游戏中最大化总和？

Question

所以，我在采访中被问到了这个问题:

有两个 friend 在玩一个游戏，他们从包含 n 个正数的数组中选择一个数字。两个 friend 一次选择一个数字，两个玩家都以最佳方式玩游戏。你必须找出游戏结束后你可以获得的最大总和(正在选择的数字)是多少。我在没有约束的情况下给出同一问题的答案后给出的约束是:

1. 在双方玩家的第一步中，他们可以选择任意数字。
2. 除了第一步之外，他们只能选择与给定数组中的前一个数字相邻的数字，并且在游戏中的那一刻之前第一名和第二名玩家尚未选择的数字。 (澄清编辑)

如果玩家无法移动，他/她就会停止游戏。当双方都无法采取行动时，游戏结束。

现在，我给出的解决方案是:

1. 创建一个包含该值以及该值在输入数组中的索引的结构。
2. 创建一个先前结构的数组，并将第一步的值存储在该数组中。
3. 根据值按非降序对该数组进行排序。
4. 开始以贪婪的方式选择一个值并打印最大值。

他们更多地寻找伪代码，尽管我也可以编写它。但是，采访者表示，在某些情况下这会失败。我想了很多关于哪些情况会失败但找不到。因此，我在这个问题上需要帮助。

另外，如果可能的话，请提供一个伪代码，说明我可以采取哪些措施来改进这一点。

编辑:我想我的问题不够清楚，特别是在第二点。面试官的意思是:

如果这不是玩家的第一步，他必须选择一个与他在之前的棋步中已经选择的数字相邻的数字。

此外，是的，两个玩家都以最佳方式玩游戏，并且轮流选择数字。

Edit2:所以，我的 friend 也问了同样的问题，但做了一些修改。他得到的不是数组，而是图表。因此，就像在我的例子中一样，我只能选择与我之前选择的索引相邻的索引，他得到的是一个无向图(邻接列表作为输入)，并且他只能选择特定移动中直接连接到先前选择的任何顶点。

例如: 假设正整数的数量是 3。这些整数的值为 4、2、4 并且，如果我命名正整数由 A、B 和 C 组成的整数，然后，

A - B
B - C

上面是我 friend 给我的例子，上面的答案是6。您能否为我指明正确的方向，告诉我如何开始？谢谢!

Answer 1

请注意，如果您在索引 x 处做出第一步，如果您的对手发挥最佳，他们的第一步将必须在索引 x-1 或 x+1。否则，他们将拥有本来可以选择但没有选择的元素。要看到这一点，请考虑两个不相邻的起点:

-------y-------------x-------

最终他们都会从数组中获取元素并最终得到如下结果:

yyyyyyyyyyyyyyxxxxxxxxxxxxxxx

因此您可以将起点重新定位到中间yx，获得相同的解决方案。

因此，假设您首先在 x 处移动。让:

s_left_x = a[0] + ... + a[x]
s_right_x = a[x] + ... a[n - 1]

s_left_y = a[0] + ... + a[x - 1]
s_right_y = a[x + 1] + ... + a[n - 1]

假设您想赢得比赛:最后的总和比对手多。如果你的对手选择x + 1，你想要s_left_x > s_right_y，如果你的对手选择x - 1，你想要s_right_x > s_left_y。这是理想的情况，为了获胜。但并不总是有可能获胜，而且你的问题不是问如何获胜，而是如何获得最大的总和。

由于你的对手会发挥最佳状态，他会迫使你陷入最坏的情况。因此，对于每个 x 作为你的第一步，你能做的最好的事情就是 min(s_left_x, s_right_x)。为每个索引 x 选择此表达式的最大值，经过一些预计算后，您可以在每个索引的 O(1) 中找到该最大值。