M.S*_*urk 3 algorithm game-theory dynamic-programming
有一个包含 N 个整数 (N < 5x10^5) 的数组，并且有两个玩家（A 和 B）依次删除该数组的元素。A 正试图使最后剩下的数字更大，而 B 正试图使其更小。
*这两名球员可以删除仅第一个元素或最后一个元素。*A首先开始删除。
让我们说; A = [3,100,4,50]
-A 将删除 50，因为如果 A 删除 3，那么 B 可以删除 100，这不是 A 想要的。
我已经通过使用动态编程解决了这个问题，但问题是内存。我使用了一个 2D 整数数组进行记忆，当我收到一个大小为 10^5 的数组时，它会消耗大量内存（对于这种情况，10^5x10^5x2 = 2x10^10 字节，即 18.6 GB。）但我想要最多使用 512 MB 内存来解决此问题。我的问题是“解决这个问题的空间效率更高的方法是什么？”。
实际上，我认为您不需要在这里进行动态编程。答案将始终是中间的元素，如果N是偶数，则答案是中间两个元素中的最大值。这是证据：
假设您是玩家A，并且您希望剩余元素大于中间元素。如果元素在数组的右半部分，你肯定会从数组的开头开始获取元素（尽可能长时间地保留你想要的元素）。现在想想玩家B会有什么反应，他为什么要帮助你实现目标？！当然，玩家B将开始从数组的末尾获取元素以摆脱您想要的大元素。
如果您是玩家B会发生同样的事情，并且您试图保留一个小于中间元素的元素，玩家A将开始从另一侧获取元素以删除您想要的小元素。
如果大元素和小元素都在数组的同一侧，则两个玩家可以计算是否可以拥有他们想要的元素。如果他们中的一个不能得到他想要的元素，他会通过总是移除另一侧的元素来推动另一个玩家确保保持中间元素。
唯一的特殊情况是如果N是偶数，在这种情况下，最后一步将由玩家A完成，并且数组将剩下2 个元素（即中间的两个元素）。在这种情况下，玩家A肯定会删除较小的元素并保留较大的元素。