👻LeetCode——可获得的最大点数
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
题目链接：可获得的最大点数https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/
题目分析：当我们拿到一道题目时，一定要去分析题目给的数据范围。这道题每张卡牌对于的点数都是正数，且k最大值为和卡牌数量一样多。所以这里我们可以马上意识到这种情况可以特判，直接返回整个数组之和。下面进行仔细分析
每次我们抽卡只能从首或尾抽，说明被我们丢弃的卡一定是连续的靠在一起的。因为我们每次都要么从最左边或者从最右边抽，直到抽够k张，那些我们不要的卡片说明就是原数组的一个子数组。
如果数组的长度为n，我们需要从n长抽够k张卡，则说明剩下的卡数量为n-k
所有卡片之和是固定的。我们想让抽的卡尽可能点数之和大，理所当然想到让剩下的卡点数小。所以这道题目转换为从数组长度为n中找到一个长度为n-k且和最小的子数组
通过上述分析，我们可以很容易判断出使用前缀和的标志，因为前缀和数组可以在O(1)的时间内得到任意一个子数组之和，我们只需要去枚举起始坐标获得所有所有长度为n-k的子数组之和，并获得最小值，用所有卡牌之和减去这个最小值即可得到答案。
方法1：前缀和
时间复杂度O(n)
class Solution { public int maxScore(int[] nums, int k) { int n=nums.length; int[] arr=new int[n+1]; //获得前缀和数组 for(int i=0;i<n;i++) arr[i+1]=arr[i]+nums[i]; //特判：k==n时直接返回所有卡牌之和即可 if(k==n) return arr[n]; //剩余卡牌也就是子数组的长度 int len=n-k; //记录最小值 int value=Integer.MAX_VALUE; //i是子数组的起始坐标，i+len-1则是子数组的结尾坐标 for(int i=0;i+len-1<n;i++){ //去更新最小值 value=Math.min(value,arr[i+len]-arr[i]); } return arr[n]-value; } }
方法2：滑动窗口
这道题的标志不仅仅是前缀和，滑动窗口也很明显。只要大家不要把注意力全放在选择的卡牌上，去思考一下未选择的卡牌。我们同样维护一个n-k大小的窗口，每次移动去更新最小值，其思路和前缀和大同小异。
class Solution { public int maxScore(int[] nums, int k) { int n=nums.length; int len=n-k; int count=0; for(int i=0;i<n-k;i++){ count+=nums[i]; } int min=count; int r=n-k; while(r<n){ count+=nums[r]; count-=nums[r-len]; r++; min=Math.min(min,count); } return Arrays.stream(nums).sum()-min; } }
题目难度不高，但是却是锻炼思维能力的一道基础题，也希望大家可以去尝试一下。
![每日一题 --- 试题 历届真题 5个砝码【第二届】【省赛】【高职组】[蓝桥][Java]](https://ucc.alicdn.com/images/user-upload-01/aaf5db1551e642c5a8ac258103f6eda6.png?x-oss-process=image/resize,h_160,m_lfit)
