DSA problem
Maximum Points You Can Obtain from Cards
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.
The key insight is to flip the problem. Instead of choosing k cards from the two ends to maximize their sum, observe that the cards you do NOT pick form a contiguous block of n - k cards in the middle. Maximizing the picked total is therefore the same as minimizing the sum of that contiguous middle block. Slide a fixed-then-shrinking window of size n - k across the array to find the minimum middle sum, and subtract it from the total to get the answer.
Examples
cardPoints = [1,2,3,4,5,6,1], k = 312cardPoints = [2,2,2], k = 24cardPoints = [9,7,7,9,7,7,9], k = 755Constraints
- 1 <= cardPoints.length <= 10^5
- 1 <= cardPoints[i] <= 10^4
- 1 <= k <= cardPoints.length
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.