发现leetcode中1423题很有意思。
1、问题描述：
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
2、分析：
问题可以抽象为，给你一个数组，你随机从数组两端一次取一个值，取到k个，
不管有多少种取法，你要保证取到的这些数字加起来值最大。
因为第一次取数，可以先从数组左边取，也可以从右边取，接着你可以继续选择从左边取或右边取。
这样左右来回横跳取值，是十分不利于与我们统计的，我们每次取了值，下次再取数组另一端的值可能最大值就更新为和更小了，
事后你才发现决策可能是错误的。
所以我们换个思路，我们取一个值，去统计数组中剩下所有元素的和。每取走一个数，剩下的元素和一定是变得更小了。
那么原问题就可以转换为，数组两端取k个值，然后统计剩下的n-k个值，具体保留哪几个连续的n-k个数使得他们的和最小。
熟悉的感觉来了，这不就是固定长度的滑动窗口吗？
进而，我们的问题就变为遍历数组，统计数组中连续n-k个元素之和。并且我们遍历数组时不断更新这个和。
从第n-k+1个元素(下标n-k)开始，更新方法：窗口的和winSum = 原winSum + 新进窗口的元素值 - 出窗口的值。
若winSum 变小了就更新这个最小值minSum，否则继续下一个元素的遍历.
遍历完成就取得了最小值了。
之后使用原数组和 totalSum - minSum 就得到了 两端k个元素的和最大。
class Solution {func maxScore(_ cardPoints: [Int], _ k: Int) -> Int {let n = cardPoints.count;let windowSize = n - k;//总和let totalSum = cardPoints.reduce(0, +);//初始窗口和var windowSum = cardPoints[0..<windowSize].reduce(0, +);//最小和默认设置为 窗口和var minSum = windowSum;if n == k {return totalSum;}// 遍历范围 windowSize..<nfor i in windowSize..<n {//窗口向右移动一格，加上新元素，减去离开窗口的元素windowSum += cardPoints[i] - cardPoints[i - windowSize];//若windowSum更小，则更新minSumif minSum > windowSum {minSum = windowSum;}}//总和减去中间 连续 n-k 张卡最小和，即为两边取k张卡的最大和return totalSum - minSum;}
}
我们使用滑动窗口遍历了一次数组，且只是用了常量个辅助变量。
所以时间复杂度：O(n),空间复杂度：O(1)。
这道题正向思考会纠结于我们每次到底是从数组头部还是尾部取值，因为情况不唯一，我们不能确保当前的取值是使得结果是最大的。
所谓正难反易。
3、还有一种思路：
我们既然是从数组头部和尾部取k个值，那么假如从头部取i个值，必然要从尾部取k-i个值。
所以我们就可以使用前缀和，后缀和。利用此消彼长的思想，枚举所有的可能，得出最大值。
这样做有一点不好，我们要用额外的空间来存储前缀和数组和后缀和数组。这也是使用空间换时间的一种思路。
前缀和有一个特点，preSum[j + 1] - preSum[i]就得到了下标i到j 这些元素的和。
提前算好前缀和，在我们需要频繁计算某段数据的和时就无须再重复计算了。
class Solution {func maxScore(_ cardPoints: [Int], _ k: Int) -> Int {let n = cardPoints.countvar prefixSum = [Int](repeating: 0, count: k + 1)var suffixSum = [Int](repeating: 0, count: k + 1)// 计算前缀和：prefixSum[i] 表示前 i 张牌的总和for i in 1...k {prefixSum[i] = prefixSum[i - 1] + cardPoints[i - 1]}// 计算后缀和：suffixSum[i] 表示后 i 张牌的总和for i in 1...k {suffixSum[i] = suffixSum[i - 1] + cardPoints[n - i]}var maxScore = 0// 枚举所有可能的组合：前 i 张 + 后 (k-i) 张for i in 0...k {let currentScore = prefixSum[i] + suffixSum[k - i]maxScore = max(maxScore, currentScore)}return maxScore}
}
需要说明的是 prefixSum的长度是n+1,prefixSum[0] = 0,意思是数组开头取0个数。prefixSum[1]就是取第0个数+取第1个数。那么取所有数，就是prefixSum[n],共n+1个元素。依次类推
suffixSum同样，suffixSum[0]表示右边取0个元素的和,也就是我们初始化的值是0，suffixSum[1]表示从数组末尾取1个元素的和+取0个元素情况下的和，suffix[2]表示nums[n-2]+nums[n-1]的和。以此类推
空间复杂度：O(n),时间复杂度：O(k)
回顾前缀和的思路，发现我们不再关心究竟怎样取数的过程，而是考虑整体就取k个值。
前缀和和后缀和组合就可以得到了所有的情况。枚举所有情况，得到最大值即可。