題目
題目連結
幾張卡牌 排成一行，每張卡牌都有一個對應的點數。點數由整數數組 cardPoints 給出。
每次行動，你可以從行的開頭或者末尾拿一張卡牌，最終你必須正好拿 k 張卡牌。
你的點數就是你拿到手中的所有卡牌的點數之和。
給你一個整數數組 cardPoints 和整數 k，請你傳回可以獲得的最大點數。
示例 1：
輸入：cardPoints = [1,2,3,4,5,6,1], k = 3
輸出：12
解釋：第一次行動，不管拿哪張牌，你的點數總是 1 。但是，先拿最右邊的卡牌将會最大化你的可獲得點數。最優政策是拿右邊的三張牌，最終點數為 1 + 6 + 5 = 12 。
示例 2：
輸入：cardPoints = [2,2,2], k = 2
輸出：4
解釋：無論你拿起哪兩張卡牌，可獲得的點數總是 4 。
示例 3：
輸入：cardPoints = [9,7,7,9,7,7,9], k = 7
輸出：55
解釋：你必須拿起所有卡牌，可以獲得的點數為所有卡牌的點數之和。
示例 4：
輸入：cardPoints = [1,1000,1], k = 1
輸出：1
解釋：你無法拿到中間那張卡牌，是以可以獲得的最大點數為 1 。
示例 5：
輸入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
輸出：202
提示：
1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length
題解模闆（C）
int maxScore(int* cardPoints, int cardPointsSize, int k){
}
解題
對于題設我們可以很明顯知道題目的目的是從一個固有的整型數組裡面從兩端取出卡牌，數量有限，同時，傳回最大取出的值，可以反過來思考題目的意思就是：
你要使得取出來的和是最大的就要使得留下來的和是最小的，大小長度是固定的，是以對于剩下的長度推演就是對于原有的最大長度減去你所要取出的部分的長度，就是剩下的長度，同時，又知道他是兩邊開始取出的，是以最後餘下的是一個連續的子數組
題設長度為cardPointSize，取出k個卡牌
就可以轉化為對這個長度為cardPointSize的數組取出其内部長度為（carrPointSize-k）的最小子數組，這就轉化成了簡單的滑動視窗了。
參考兩天前的題目，這個就很簡單了
int maxScore(int* cardPoints, int cardPointsSize, int k){
int sum = 0;
int all=0;
for( int i = 0; i < cardPointsSize ; i++)
all += cardPoints[i];//計算所有總和
for( int i = 0; i < cardPointsSize - k; i++)
{
sum += cardPoints[i];//計算第一視窗和
printf("sum=%d ,",sum);
}
int minsum= sum;//暫得最小值
for(int i = cardPointsSize - k; i < cardPointsSize; i++)
{
sum = sum - cardPoints[i - cardPointsSize+k]+cardPoints[i];//以固定長度滑動視窗
printf("sum=%d ,",sum);
minsum = fmin(sum ,minsum);//視窗最小值更新
printf("minsum=%d ;",minsum);
}
return (all-minsum);
}
想要自己測試的小夥伴可以拷貝下面的代碼在自己的編譯器上測試
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int maxScore(int* cardPoints, int cardPointsSize, int k);
int main()
{
int cardPoints[]={1,79,80,1,1,1,200,1};
int max=maxScore(cardPoints,8,3);
printf("%d",max);
}
int maxScore(int* cardPoints, int cardPointsSize, int k){
int sum = 0;
int all=0;
for( int i = 0; i < cardPointsSize ; i++)
all += cardPoints[i];//計算所有總和
for( int i = 0; i < cardPointsSize - k; i++)
{
sum += cardPoints[i];//計算第一視窗和
printf("sum=%d ,",sum);
}
int minsum= sum;//暫得最小值
for(int i = cardPointsSize - k; i < cardPointsSize; i++)
{
sum = sum - cardPoints[i - cardPointsSize+k]+cardPoints[i];//以固定長度滑動視窗
printf("sum=%d ,",sum);
minsum = fmin(sum ,minsum);//視窗最小值更新
printf("minsum=%d ;",minsum);
}
return (all-minsum);
}
再貼上一張運作圖，截取了最好看的資料