可獲得的最大點數
問題：
幾張卡牌 排成一行，每張卡牌都有一個對應的點數，點數由整數陣列 cardPoints 給出，
每次行動，你可以從行的開頭或者末尾拿一張卡牌，最終你必須正好拿 k 張卡牌，
你的點數就是你拿到手中的所有卡牌的點數之和，
給你一個整數陣列 cardPoints 和整數 k，請你回傳可以獲得的最大點數，
思路：
- 由于拿牌的位置處在前后，所以剩下牌（數量是 len - k 張）都是連續的，
- 所以只需求出陣列中連續元素和最小的片段，
- 再用總合減去則為可以獲得的最大點數，
class Solution {
public:
int maxScore(const vector<int>& cardPoints, int& k) const {
auto len = cardPoints.size();
k = len - k;
auto sumk = 0;
auto temp = k;
while(temp-- > 0) sumk += cardPoints[temp];
auto tempsum = sumk;
for(auto i = k; i < len; ++i) {
sumk = sumk - cardPoints[i - k] + cardPoints[i];
tempsum = min(tempsum, sumk);
}
auto sum = 0;
while(len-- > 0) sum += cardPoints[len];
return sum - tempsum;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257349.html
標籤：其他
下一篇：合成大西瓜自制版教程