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 <= 1051 <= cardPoints[i] <= 1041 <= k <= cardPoints.lengthThe primary observation is that by taking k cards from either end, you are essentially leaving n-k cards behind. Thus, instead of focusing on maximally acquiring k cards, focus on finding the minimum sum of n-k cards that are left unused.
Calculate the total sum of card points, then utilize a sliding window of size n-k to find the minimum sum of that window. Finally, subtract this minimum sum from the total sum to get the maximum score you can obtain by taking k cards.
The function calculates the total sum of the array and then finds the minimal sum of any subarray of length n-k using a sliding window. This sliding window allows us to efficiently find which elements to leave behind, thus maximizing the cards taken. The remaining cards' minimum sum is subtracted from the total to give the optimal score.
Java
Time Complexity: O(n), where n is the length of cardPoints, because we traverse the list once for the sliding window.
Space Complexity: O(1), as no additional space proportional to the input size is used.
This approach involves calculating the prefix sums from the start and suffix sums from the end of the cardPoints array. By doing so, you can easily compute what the score would be when selecting a certain number of cards from the start and remaining cards from the end, iterating such that the using combinations of these selections.
A loop over k possible selections computes maximum scores from k elements chosen such that some are prefix and the rest are suffix.
The C++ solution involves initiating prefix and suffix arrays that hold summed values progressively such that each index i in either array holds the sum of the first i or last i elements of the main array. Then a loop is used to check each possible distribution of cards between prefix and suffix to find and combine the maximum scores achievable with k moves.
C#
Time Complexity: O(k), because we are computing prefix and suffix sums for k cards and then comparing these sums k times.
Space Complexity: O(k), due to the storage of prefix and suffix sums in two arrays of length k.
| Approach | Complexity |
|---|---|
| Sliding Window to Minimize Unused Cards | Time Complexity: O(n), where n is the length of cardPoints, because we traverse the list once for the sliding window. Space Complexity: O(1), as no additional space proportional to the input size is used. |
| Prefix and Suffix Sums | Time Complexity: O(k), because we are computing prefix and suffix sums for k cards and then comparing these sums k times. Space Complexity: O(k), due to the storage of prefix and suffix sums in two arrays of length k. |
L2. Maximum Points You Can Obtain from Cards | 2 Pointers and Sliding Window Playlist • take U forward • 159,010 views views
Watch 9 more video solutions →Practice Maximum Points You Can Obtain from Cards with our built-in code editor and test cases.
Practice on FleetCode