# C++ Solution to Coding Challenge 1423. Maximum Points You Can Obtain from Cards

Oct 13, 2022·

### Problem statement

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array `cardPoints`.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly `k` cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array `cardPoints` and the integer `k`, return the maximum score you can obtain.

#### Example 1

``````Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.
``````

#### Example 2

``````Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.
``````

#### Example 3

``````Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.
``````

#### Constraints

• `1 <= cardPoints.length <= 10^5`.

• `1 <= cardPoints[i] <= 10^4`.

• `1 <= k <= cardPoints.length`.

### Solution 1: Compute the sums of `k` consecutive cards of interest

Assume there are `N` cards in `cardPoints`. You might be interested in only `2k` cards in this problem.

Any card you take is either in the first `k` cards `cardPoints[0, ..., k-1]` or in the last `k` cards `cardPoints[N-k, ..., N-1]`.

If you concatenate the last part with the first one like this `cardPoints[N-k, ..., N-1, 0, ..., k-1]`, the problem turns into computing the maximum sum of the `k` consecutive cards in that new array.

#### Example 1

For `cardPoints = [1,2,3,4,5,6,1]` and `k = 3`, concatenating the last `3` cards with the first `3` cards you get the array `[5,6,1,1,2,3,4]`.

The maximum sum of the `3` consecutive cards is `sum([5,6,1]) = 12`.

#### Code

``````#include <iostream>
#include <vector>
using namespace std;
int maxScore(vector<int>& cardPoints, int k) {
vector<int> cards(cardPoints.end() - k, cardPoints.end());
cards.insert(cards.end(), cardPoints.begin(), cardPoints.begin() + k);
int maxSum = 0;
for (int i = 0; i <= k; i++) {
int sum = 0;
for (int j = 0; j < k; j++) {
sum += cards[i + j];
}
maxSum = max(maxSum, sum);
}
return maxSum;
}
int main() {
vector<int> cardPoints{1,2,3,4,5,6,1};
cout << maxScore(cardPoints, 3) << endl;
cardPoints = {2,2,2};
cout << maxScore(cardPoints, 2) << endl;
cardPoints = {9,7,7,9,7,7,9};
cout << maxScore(cardPoints, 7) << endl;
}
``````
``````Output:
12
4
55
``````

#### Complexity

• Runtime: `O(k^2)`.

• Extra space: `O(2k)`.

### Solution 2: Improve the performance

When `k` is large (it can equal `cardPoints.length`), the solution above is slow due to runtime complexity `O(k^2)`.

It is because there are many recomputations when computing the `sum` of each `k` consecutive cards.

You can save this runtime by keeping the common `(k-1)`-sum between two neighbor `k`-sums.

#### Example 1

The sum `6 + 1` are computed in both sums `5 + 6 + 1` and `6 + 1 + 1` in the array `[5,6,1,1,2,3,4]`.

Assume you have computed the sum `5 + 6 + 1 = 12`. To compute the next sum `6 + 1 + 1`, keep the sum `6 + 1` from previous one by subtracting `12 - 5 = 7`. Then add it with the new card's points `7 + 1 = 8`.

The value `k` in this example is not too large to see the effect but I believe you can see how it helps when `k` is very large.

On the other hand, you do not have to use extra space for the concatenation. You can use the modulo operator `%` on the indices.

#### Code

``````#include <iostream>
#include <vector>
using namespace std;
int maxScore(vector<int>& cardPoints, int k) {
int maxSum = 0;
int sum = 0;
// Compute the sum of the last k cards
for (int i = cardPoints.size() - k; i < cardPoints.size(); i++) {
sum += cardPoints[i];
}
maxSum = max(maxSum, sum);
// Compute the other sums
for (int i = cardPoints.size() - k + 1; i <= cardPoints.size(); i++) {
sum = sum - cardPoints[i - 1] + cardPoints[(i - 1 + k) % cardPoints.size()];
maxSum = max(maxSum, sum);
}
return maxSum;
}
int main() {
vector<int> cardPoints{1,2,3,4,5,6,1};
cout << maxScore(cardPoints, 3) << endl;
cardPoints = {2,2,2};
cout << maxScore(cardPoints, 2) << endl;
cardPoints = {9,7,7,9,7,7,9};
cout << maxScore(cardPoints, 7) << endl;
}
``````
``````Output:
12
4
55
``````

#### Complexity

• Runtime: `O(k)`.

• Extra space: `O(1)`.

### References

Get my FREE book "10 Classic Coding Challenges"