最开始使用 DP ，因为题目中给的问题空间范围较大，缓存使用数组的话对连续的内存空间要求过高。故采用 hash 表做缓存：
public int maxScore(int[] cardPoints, int k) { int length = cardPoints.length; Map<String, Integer> cache = new HashMap<String, Integer>(); return maxScoreDP(cardPoints, k, 0, length - 1, cache); } public int maxScoreDP(int[] cardPoints, int k, int begin, int end, Map<String, Integer> cache) { if (k == 0 || end < begin) { return 0; } String flag = String.valueOf(k) + "," + String.valueOf(begin) + "," + String.valueOf(end); if (cache.keySet().contains(flag)) { return cache.get(flag); } int holdS = maxScoreDP(cardPoints, k - 1, begin + 1, end, cache) + cardPoints[begin]; int holdE = maxScoreDP(cardPoints, k - 1, begin, end - 1, cache) + cardPoints[end]; int re = Math.max(holdS, holdE); cache.put(flag, re); return re; }
进过测试，计算结果是没问题的，但还是超时了。该问题对时间复杂度要求较高。
换一种思路，首尾和最大，就是首尾夹住的中间的连续子数组和最小。我们将中间子数据看做一个窗口，不断从数组头部向尾部移动，求出最小值，从数组所有元素的和中减去这个最小值便能得到首尾的最大值。
/** * @Author Nxy * @Date 2020/5/8 19:34 * @Description 滑动窗口 */ public final int maxScore2(int[] cardPoints, int k) { int length = cardPoints.length; int min = Integer.MAX_VALUE; for (int i = 0; i <= k; i++) { int temp = 0; for (int j = 0; j < length - k; j++) { temp += cardPoints[i + j]; } min = Math.min(min, temp); } int nums = 0; for (int i = 0; i < length; i++) { nums += cardPoints[i]; } return nums - min; }
再优化一下，窗口滑动时并不需要重新对窗口内的元素求和，只需减去头部元素的值并加上与尾部相邻的下一个值即可。让窗口不断沿数组向后嗅探：
/** * @Author Nxy * @Date 2020/5/8 19:34 * @Description 滑动窗口升级版 */ public final int maxScore3(int[] cardPoints, int k) { int length = cardPoints.length; int nums = 0; for (int i = 0; i < length; i++) { nums += cardPoints[i]; } int windowVal = 0; for (int i = 0; i < length - k; i++) { windowVal += cardPoints[i]; } int min = windowVal; for (int i = length - k; i < length; i++) { windowVal += cardPoints[i]; windowVal -= cardPoints[i - length + k]; min = Math.min(min, windowVal); } return nums - min; }
最终解法效果：
原文：https://www.cnblogs.com/niuyourou/p/12853102.html