思路:

你是不是跟我一样，拿到今天题目的第一想法是模拟题目取卡牌的过程呢？模拟的方法可以用递归。但是递归的过程是把所有的可能组合方式都求了一遍，时间复杂度会达到 O(N*k) ，在题目所给出的 10 ^ 5 的数据规模下，会超时。

下面的代码是我用的递归+记忆化的方式写的，虽然有记忆化，但是因为没有降低时间复杂度，所以仍然超时。提供在这里仅供大家参考。欢迎大家提供能 AC 的递归方法。

我定义的递归函数 dfs(cardPoints, i, j, k) ，表示在 cardPoints 的第 i ~ j 的位置中（包含i,j），从两端抽取 k 个卡牌能够获得的最大点数。那么当 k == 0 的时候，说明不抽牌，结果是 0。当 k != 0 的时候，抽取 k 个卡牌能拿到的点数等于 max(抽取最左边卡牌的点数 + 剩余卡牌继续抽获得的最大点数, 抽取最右边卡牌的点数 + 剩余卡牌继续抽获得最大点数)。

代码:

当数据规模到达了 10 ^ 5 ，已经在提醒我们这个题应该使用 O(N) 的解法。

把今天的这个问题思路整理一下，题目等价于：求从 cardPoints 最左边抽 i 个数字，从 cardPoints 最右边抽取 k - i 个数字，能抽取获得的最大点数是多少。

一旦这么想，立马柳暗花明：抽走的卡牌点数之和 = cardPoints 所有元素之和 - 剩余的中间部分元素之和。

我们同样使用模拟法，但是比递归方法高妙的地方在，我们一次性从左边抽走 i 个数字： i 从 0 到 k 的遍历，表示从左边抽取了的元素数，那么从右边抽取的元素数是 k - i 个。现在问题是怎么快速求 剩余的中间部分元素之和？

求区间的和可以用 preSum 。 preSum 方法还能快速计算指定区间段 i ~ j 的元素之和。它的计算方法是从左向右遍历数组，当遍历到数组的 i 位置时， preSum 表示 i 位置左边的元素之和。

假设数组长度为 N ，我们定义一个长度为 N+1 的 preSum 数组， preSum[i] 表示该元素左边所有元素之和（不包含当前元素）。然后遍历一次数组，累加区间 [0, i) 范围内的元素，可以得到 preSum 数组。

代码如下：

利用 preSum 数组，可以在 O(1) 的时间内快速求出 nums 任意区间 [i, j] (两端都包含) 的各元素之和。

综合以上的思路，我们的想法可以先求 preSum ，然后使用一个 0 ~ k 的遍历表示从左边拿走的元素数，然后根据窗口大小 windowSize = N - k ，利用 preSum 快速求窗口内元素之和。

代码:

在上面的 preSum 中，我们已经想到了，抽走的卡牌点数之和 = cardPoints 所有元素之和 - 剩余的中间部分元素之和。在 preSum 的代码里，我们是模拟了从左边拿走 i 个卡牌的过程。事实上，我们也可以直接求剩余的中间部分元素之和的最小值。只要剩余的卡牌点数之和最小，那么抽走的卡牌点数之和就最大！

求一个固定大小的窗口中所有元素之和的最小值——这是一个滑动窗口问题！与这个问题非常类似的就是643. 子数组最大平均数 I。

把剩余的中间部分元素抽象成长度固定为 windowSize = N - k 的滑动窗口。当每次窗口右移的时候，需要把右边的新位置 加到 窗口中的 和 中，把左边被移除的位置从窗口的 和 中 减掉。这样窗口里面所有元素的 和 是准确的，我们求出最大的和，最终除以 k 得到最大平均数。

这个方法只用遍历一次数组。

需要注意的是，需要根据 i 的位置，计算滑动窗口是否开始、是否要移除最左边元素：

• 当 i >= windowSize 时，为了固定窗口的元素是 k 个，每次移动时需要将 i - windowSize 位置的元素移除。
• 当 i >= windowSize - 1 时，滑动窗口内的元素刚好是 k 个，开始计算滑动窗口的最小和。

最后，用 cardPoints 的所有元素之和，减去滑动窗口内的最小元素和，就是拿走的卡牌的最大点数。

代码: