Maximum Points You Can Obtain from Cards

77.4k
0

Given an integer array cardPoints and an integer k, you have to pick exactly k cards.

In one move, you can pick a card either from the beginning or from the end of the array.

Return the maximum score you can obtain after picking exactly k cards.

Example 1

Input: cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3

Output: 12

Explanation: We can pick 6 and 1 from the end, and 5 from the end before them. The selected cards are 5, 6, and 1. Their total score is 12.

Example 2

Input: cardPoints = [2, 2, 2], k = 2

Output: 4

Explanation: Any two cards can be picked, and the maximum score will be 4.

Example 3

Input: cardPoints = [9, 7, 7, 9, 7, 7, 9], k = 7

Output: 55

Explanation: Since k is equal to the number of cards, all cards are picked. The total score is 55.

Brute Force Approach

Every valid selection contains some cards from the left end and the remaining cards from the right end. For k selections, the number of left cards can range from 0 to k.

Each possible split can be evaluated independently by recalculating the corresponding left and right sums. Complete split examination guarantees the maximum score, but repeated summation increases the running time.

Algorithm

  • Store the array size in n and return -1 when k < 0 or k > n.

  • Return 0 when k equals 0, and return the total array sum when k equals n.

  • Initialize maxScore with the smallest possible value to support negative card values.

  • Traverse leftCount from 0 to k and calculate rightCount = k - leftCount.

  • Add the first leftCount values and the final rightCount values to obtain currentScore.

  • Update maxScore with the larger value between maxScore and currentScore, then return maxScore after checking every split.

Dry Run

Maximum Points You Can Obtain from Cards Brute Force Dry Run.png

Maximum Points You Can Obtain from Cards Brute Force Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the maximum score by evaluating every left-right split.
int maxScore(vector<int>& cardPoints, int k) {
int n = cardPoints.size();
// Invalid k cannot form a valid selection.
if (k < 0 || k > n) {
return -1;
}
// Picking no cards gives a score of zero.
if (k == 0) {
return 0;
}
// Picking all cards requires the complete array sum.
if (k == n) {
return accumulate(cardPoints.begin(), cardPoints.end(), 0);
}
int maxScore = INT_MIN;
// Try every possible number of cards taken from the left.
for (int leftCount = 0; leftCount <= k; leftCount++) {
int rightCount = k - leftCount;
int currentScore = 0;
// Add the selected cards from the left end.
for (int i = 0; i < leftCount; i++) {
currentScore += cardPoints[i];
}
// Add the remaining selected cards from the right end.
for (int i = 0; i < rightCount; i++) {
currentScore += cardPoints[n - 1 - i];
}
// Keep the best score among all valid splits.
if (currentScore > maxScore) {
maxScore = currentScore;
}
}
return maxScore;
}
};
int main() {
vector<int> cardPoints = {1, 2, 3, 4, 5, 6, 1};
int k = 3;
Solution solution;
cout << solution.maxScore(cardPoints, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(K²), because K + 1 splits receive examination and up to K selected values may require summation for every split.

Space Complexity: O(1), because only counters and sum variables require auxiliary storage.

Better Approach

Repeated summation can be removed by precomputing scores for every possible number of cards selected from each end.

Array leftSum stores sums of the first i cards, while rightSum stores sums of the final i cards. Any split score can then be obtained in constant time by combining one prefix value and one suffix value.

Algorithm

  • Store the array size in n and return -1 when k < 0 or k > n.

  • Return 0 when k equals 0, and return the total array sum when k equals n.

  • Create leftSum and rightSum with size k + 1, with position 0 initialized to 0.

  • Build leftSum[i] using the first i cards and rightSum[i] using the final i cards.

  • Traverse leftCount from 0 to k, calculate rightCount = k - leftCount, and obtain currentScore = leftSum[leftCount] + rightSum[rightCount].

  • Update maxScore for every split and return maxScore after complete traversal.

Dry Run

Maximum Points You Can Obtain from Cards Better Appraoch Dry Run.png

Maximum Points You Can Obtain from Cards Better Appraoch Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the maximum score using precomputed left and right sums.
int maxScore(vector<int>& cardPoints, int k) {
int n = cardPoints.size();
// Invalid k cannot form a valid selection.
if (k < 0 || k > n) {
return -1;
}
// Picking no cards gives a score of zero.
if (k == 0) {
return 0;
}
// Picking all cards requires the complete array sum.
if (k == n) {
return accumulate(cardPoints.begin(), cardPoints.end(), 0);
}
vector<int> leftSum(k + 1, 0);
vector<int> rightSum(k + 1, 0);
// Store sums for every possible number of left cards.
for (int i = 1; i <= k; i++) {
leftSum[i] = leftSum[i - 1] + cardPoints[i - 1];
}
// Store sums for every possible number of right cards.
for (int i = 1; i <= k; i++) {
rightSum[i] = rightSum[i - 1] + cardPoints[n - i];
}
int maxScore = INT_MIN;
// Combine each valid left count with its matching right count.
for (int leftCount = 0; leftCount <= k; leftCount++) {
int rightCount = k - leftCount;
int currentScore =
leftSum[leftCount] + rightSum[rightCount];
// Keep the maximum score among all possible splits.
if (currentScore > maxScore) {
maxScore = currentScore;
}
}
return maxScore;
}
};
int main() {
vector<int> cardPoints = {1, 2, 3, 4, 5, 6, 1};
int k = 3;
Solution solution;
cout << solution.maxScore(cardPoints, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(K), because construction of both sum arrays and examination of all K + 1 splits require linear time.

Space Complexity: O(K), because leftSum and rightSum each contain K + 1 values.

Optimal Approach

Selecting the first k cards forms one valid split. Replacing one selected left card with one card from the right creates the next possible split.

Every replacement removes the rightmost card from the current left selection and adds the next available card from the right end. Repeating the replacement k times generates all possible left-right distributions without extra arrays.

Algorithm

  • Store the array size in n and return -1 when k < 0 or k > n.

  • Return 0 when k equals 0, and return the total array sum when k equals n.

  • Calculate the sum of the first k cards and store the result in currentScore.

  • Initialize maxScore with currentScore and rightIndex with n - 1.

  • Traverse leftIndex from k - 1 down to 0. During each step, subtract cardPoints[leftIndex] because that card leaves the left selection, add cardPoints[rightIndex] because the next card from the right enters the selection, then decrement rightIndex.

  • Update maxScore after every replacement, then return maxScore after generating all possible splits.

Dry Run

Maximum Points You Can Obtain from Cards Optimal Appraoch Dry Run.png

Maximum Points You Can Obtain from Cards Optimal Appraoch Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Finds the maximum score by shifting selections between both ends.
int maxScore(vector<int>& cardPoints, int k) {
int n = cardPoints.size();
// Invalid k cannot form a valid selection.
if (k < 0 || k > n) {
return -1;
}
// Picking no cards gives a score of zero.
if (k == 0) {
return 0;
}
// Picking all cards requires the complete array sum.
if (k == n) {
return accumulate(cardPoints.begin(), cardPoints.end(), 0);
}
int currentScore = 0;
// Start with all k selected cards taken from the left.
for (int i = 0; i < k; i++) {
currentScore += cardPoints[i];
}
int maxScore = currentScore;
int rightIndex = n - 1;
// Replace one left card with one right card in each step.
for (int leftIndex = k - 1; leftIndex >= 0; leftIndex--) {
currentScore -= cardPoints[leftIndex];
currentScore += cardPoints[rightIndex];
rightIndex--;
// Keep the best score after each new split.
if (currentScore > maxScore) {
maxScore = currentScore;
}
}
return maxScore;
}
};
int main() {
vector<int> cardPoints = {1, 2, 3, 4, 5, 6, 1};
int k = 3;
Solution solution;
cout << solution.maxScore(cardPoints, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(K), because the first K cards require one summation and K replacements generate all remaining splits.

Space Complexity: O(1), because only score variables and index variables require auxiliary storage.

FAQS

Q1. Why does every valid selection correspond to a left-right split?

Card removal is allowed only from either end. After exactly K removals, selected cards must contain a prefix, a suffix, or a combination of both.

Q2. Why does the Brute Force Approach require O(K²) time?

Every one of the K + 1 splits recalculates up to K selected values.

Q3. Why do prefix and suffix sums improve the Better Approach?

Precomputed sums provide every split score through two array accesses and one addition.

Q4. Why does the Optimal Approach begin with the first K cards?

Starting with the first K cards is only one convenient choice. We can also begin with the last K cards and gradually replace cards from the right selection with cards from the beginning. Both directions generate all K + 1 possible left-right splits and give the same O(K) time and O(1) auxiliary space.

Q5. Why does every replacement preserve exactly K selected cards?

One selected left card leaves the score while one right card enters the score during the same step.

Q6. Does the method support negative card values?

Yes. Initializing maxScore from a valid selection prevents an incorrect default score of 0 when every valid score is negative.

Sliding WindowArrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0