幾張卡牌 排成一行,每張卡牌都有一個對應的點數。點數由整數數組 cardPoints 給出。
每次行動,你可以從行的開頭或者末尾拿一張卡牌,最終你必須正好拿 k 張卡牌。
你的點數就是你拿到手中的所有卡牌的點數之和。
給你一個整數數組 cardPoints 和整數 k,請你返回可以獲得的最大點數。
示例 1:
輸入:cardPoints = [1,2,3,4,5,6,1], k = 3
輸出:12
解釋:第一次行動,不管拿哪張牌,你的點數總是 1 。但是,先拿最右邊的卡牌將會最大化你的可獲得點數。最優策略是拿右邊的三張牌,最終點數為 1 + 6 + 5 = 12 。
代碼
class Solution {public int maxScore(int[] cardPoints, int k) {//將題目轉化為求累加和最小的滑動窗口int l=0,r=0,n=cardPoints.length,tar=n-k,cur=0;for(;r<tar;r++)//初始化第一個滑動窗口cur+=cardPoints[r];int res=cur;while (r<n){cur-=cardPoints[l++];cur+=cardPoints[r++]; res= Math.min(res,cur);}int sum=Arrays.stream(cardPoints).sum();return sum-res;}
}