LeetCode 1423. Maximum Points You Can Obtain from Cards

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        const int n = cardPoints.size();
        int windowSize = n - k;
        int currWindowSum = accumulate(cardPoints.begin(), cardPoints.begin() + windowSize, 0);
        int sum = currWindowSum, minWindowSum = currWindowSum;
        for (int i = windowSize; i < n; ++i) {
            sum += cardPoints[i];
            currWindowSum += cardPoints[i] - cardPoints[i - windowSize];
            minWindowSum = min(minWindowSum, currWindowSum);
        }
        return sum - minWindowSum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        const int n = cardPoints.size();
        // take 'i' card(s) from left (and 'k - i' card(s) from right),
        // how many points could we get. i = 0 at first.
        int dp = accumulate(cardPoints.rbegin(), cardPoints.rbegin() + k, 0);
        int maxPoints = dp, idxDiff = n - k;
        for (int i = 0; i < k; ++i) {
            dp = dp + cardPoints[i] - cardPoints[i + idxDiff];
            maxPoints = max(maxPoints, dp);
        }
        return maxPoints;
    }
};