Maximum Points You Can Obtain from Cards - Practice Coding Problems

Maximum Points You Can Obtain from Cards - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: 12

💡 Note: Take 3 cards from right end: [5,6,1] gives sum = 12. This is better than other combinations like taking 1 from left [1] and 2 from right [6,1] which gives 1+6+1=8.

Example 2 — Mixed Selection

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

› Output: 4

💡 Note: Can take 2 cards from left [2,2] = 4, or 2 cards from right [2,2] = 4, or 1 from each end [2,2] = 4. All give the same result.

Example 3 — All Cards

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

› Output: 55

💡 Note: Take all cards since k equals array length: 9+7+7+9+7+7+9 = 55

Constraints

1 ≤ cardPoints.length ≤ 10⁵
1 ≤ cardPoints[i] ≤ 10⁴
1 ≤ k ≤ cardPoints.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array of card points and k cards to pick

Process

Try different combinations of left and right selections

Output

Maximum possible sum from k edge cards

Key Takeaway

🎯 Key Insight: Maximum edge sum = Total sum - Minimum middle sum (sliding window approach)

Asked in

A Amazon 15 M Microsoft 12 G Google 8 F Facebook 6

The key insight is that maximizing k cards from edges equals minimizing n-k cards from the middle. Best approach uses sliding window to find minimum sum of middle cards in O(n) time. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Optimization	O(k²)	O(n)	Precompute prefix sums to avoid recalculating left sums repeatedly
Sliding Window (Optimal)	O(n)	O(1)	Find minimum sum of n-k middle cards to maximize k edge cards
Brute Force - Try All Combinations	O(k²)	O(1)	Try every possible way to pick i cards from left and k-i cards from right

Prefix Sum Optimization — Algorithm Steps

Step 1: Build prefix sum array for quick left sum lookup
Step 2: For each split, use prefix sum for left and calculate right sum
Step 3: Track maximum sum across all valid splits

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Prefix

Precompute cumulative sums: [0,1,3,6,10,15,21]

Quick Lookup

Left sum = prefix[i], Right sum = total - prefix[n-(k-i)]

Find Max

Compare all combinations efficiently

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* cardPoints, int n, int k) {
    // Build prefix sum array
    int* prefix = (int*)calloc(n + 1, sizeof(int));
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + cardPoints[i];
    }
    
    int maxSum = 0;
    
    // Try all combinations: i cards from left, k-i cards from right
    for (int i = 0; i <= k; i++) {
        int leftSum = prefix[i];
        int rightSum = prefix[n] - prefix[n - (k - i)];
        if (leftSum + rightSum > maxSum) {
            maxSum = leftSum + rightSum;
        }
    }
    
    free(prefix);
    return maxSum;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int cardPoints[100];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL && strlen(token) > 0) {
        cardPoints[n++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%d\n", solution(cardPoints, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k²)

k iterations, each calculating right sum takes O(k) time

✓ Linear Growth

Space Complexity

O(n)

Prefix sum array stores cumulative sums for all elements

⚡ Linearithmic Space

89.0K Views

Medium Frequency

~15 min Avg. Time

2.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler