PPractick

The problem

In a card game, cards lie in a row with point values, and on each turn you take one card from either end. After exactly k turns, your score is the sum of the cards taken. Whatever the order, the result is always "some i cards from the left plus k − i from the right", for some i from 0 to k. So start with the first k cards and repeatedly swap the innermost left card for the next card from the right end, tracking the best sum. Equivalently: the cards you leave form a contiguous window of n − k cards, so minimise that window's sum.

Example: [1, 2, 3, 4, 5, 6, 1], k = 3 → 12 (take 1, 6, 5 from the right).

Function signature

long long maxScore(const vector<int>& cardPoints, int k);  // 1 <= k <= n

Test cases

Input (cards, k)	Output	Explanation
([1, 2, 3, 4, 5, 6, 1], 3)	12	1 + 6 + 5
([2, 2, 2], 2)	4
([9, 7, 7, 9, 7, 7, 9], 7)	55	Take everything
([1, 1000, 1], 1)	1	1000 is out of reach
([1, 79, 80, 1, 1, 1, 200, 1], 3)	202	1 + 200 + 1

(Confirm: exactly k cards are taken, each from the current left or right end; points are positive.)

How interviewers phrase it

• "You can take one card from the beginning or the end of the row each step, exactly k times. Return the maximum score" (LeetCode 1423).

Clarifying questions to ask

1. Exactly k cards? (Yes.)
2. Can k equal n? (Yes: take everything.)
3. Are points non-negative? (Yes, but the approach doesn't depend on it.)

Follow-ups to expect

1. "Why only k + 1 possibilities?"
2. "What's the complement view?"
3. "Why doesn't greedy (take the larger end each time) work?"
4. "Can you avoid prefix arrays?"
5. "Complexity?"

Related questions

• Longest subarray with given sum K (positives) Medium
• Binary Subarrays With Sum Hard
• Count number of Nice subarrays Hard
• Longest subarray with sum K Medium
• Count subarrays with given sum Medium
• Largest Subarray with Sum 0 Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in