思路:
你是不是跟我一样，拿到今天题目的第一想法是模拟题目取卡牌的过程呢？模拟的方法可以用递归。但是递归的过程是把所有的可能组合方式都求了一遍，时间复杂度会达到 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 的所有元素之和，减去滑动窗口内的最小元素和，就是拿走的卡牌的最大点数。
代码: