{x}
blog image

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.

 

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 <= 105
  • 1 <= cardPoints[i] <= 104
  • 1 <= k <= cardPoints.length

1423. Maximum Points You Can Obtain from Cards

Problem Description

Given an integer array cardPoints representing the points on cards arranged in a row, and an integer k representing the number of cards you can take, you need to find the maximum score you can obtain. In each step, you can take one card from either the beginning or the end of the row.

Solution: Sliding Window

The most efficient approach to solve this problem is using a sliding window technique. Here's a breakdown:

  1. Calculate Initial Score: First, calculate the sum of points from the last k cards. This represents the initial score if you choose to take only from the right end.

  2. Sliding Window: Now, iterate through the first k cards. For each card you take from the left (cardPoints[i]), you must simultaneously remove a card from the right (cardPoints[n - k + i], where n is the length of the array). This maintains a constant window size of k.

  3. Update Maximum Score: In each iteration, update the current score (s) by adding the card taken from the left and subtracting the card removed from the right. Keep track of the maximum score (ans) encountered so far.

  4. Return Maximum Score: After the loop completes, return the maximum score ans.

Time and Space Complexity

  • Time Complexity: O(k). The sliding window iterates through the first k elements of the array.
  • Space Complexity: O(1). We use only a few constant extra variables.

Code Implementation (Python)

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        s = sum(cardPoints[n - k:])  # Initial score from the right
        ans = s
        for i in range(k):
            s += cardPoints[i] - cardPoints[n - k + i]  # Update score with sliding window
            ans = max(ans, s)  # Update maximum score
        return ans

Code Implementation in Other Languages

The approach remains the same across different languages; only the syntax changes slightly. Refer to the solution section of the original response for code in Java, C++, Go, TypeScript, Rust, JavaScript, C#, PHP, Scala, Swift, Ruby, Kotlin, and Dart. Each implementation follows the same sliding window logic described above.

Example Walkthrough

Let's consider the example cardPoints = [1,2,3,4,5,6,1], k = 3.

  1. Initial Score: s = sum([4, 5, 6, 1]) = 16 (This is incorrect. It should be sum([5,6,1])=12. There's a slight error in the original response's example calculation). ans = 12

  2. Iteration 1 (i=0):

    • s += cardPoints[0] - cardPoints[4] which is 12 + 1 - 5 = 8
    • ans = max(12, 8) = 12

  3. Iteration 2 (i=1):

    • s += cardPoints[1] - cardPoints[3] which is 8 + 2 - 4 = 6
    • ans = max(12, 6) = 12

  4. Iteration 3 (i=2):

    • s += cardPoints[2] - cardPoints[2] which is 6 + 3 - 3 = 6
    • ans = max(12,6) = 12

The maximum score remains 12 throughout the process.

This sliding window approach provides an efficient solution to the problem, avoiding the need for computationally expensive brute-force or recursive methods. The corrected initial score calculation in step 1 addresses an inaccuracy present in the original response.