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: cardPoints = [1,2,3,4,5,6,1], k = 3 Output: 12

Example 2: cardPoints = [2,2,2], k = 2 Output: 4

Example 3: cardPoints = [9,7,7,9,7,7,9], k = 7 Output: 55

def max_score(cardPoints, k):
    n = len(cardPoints)
    total_sum = sum(cardPoints)
    window_size = n - k
    current_sum = sum(cardPoints[:window_size])
    min_sum = current_sum

    for i in range(window_size, n):
        current_sum += cardPoints[i] - cardPoints[i - window_size]
        min_sum = min(min_sum, current_sum)

    return total_sum - min_sum


# Example Usage
cardPoints1 = [1, 2, 3, 4, 5, 6, 1]
k1 = 3
print(f"Maximum score for cardPoints {cardPoints1} and k={k1}: {max_score(cardPoints1, k1)}")

cardPoints2 = [2, 2, 2]
k2 = 2
print(f"Maximum score for cardPoints {cardPoints2} and k={k2}: {max_score(cardPoints2, k2)}")

cardPoints3 = [9, 7, 7, 9, 7, 7, 9]
k3 = 7
print(f"Maximum score for cardPoints {cardPoints3} and k={k3}: {max_score(cardPoints3, k3)}")

Explanation:

1. Problem Understanding:

   • We are given an array cardPoints representing points associated with cards arranged in a row.
   • We need to take exactly k cards from either the beginning or the end of the row.
   • Our goal is to maximize the sum of points of the cards we take.

2. Naive Approach (Brute Force):

   • Try all possible combinations of taking k cards from the beginning and end.
   • Calculate the score for each combination and return the maximum score.
   • This approach has a time complexity of O(k), because in the worst case, we will have to try out all combinations of k elements.

   def max_score_brute_force(cardPoints, k):
       n = len(cardPoints)
       max_score = 0
       for i in range(k + 1):
           current_score = sum(cardPoints[:i]) + sum(cardPoints[n - (k - i):])
           max_score = max(max_score, current_score)
       return max_score
   

3. Optimal Approach (Sliding Window):

   • Instead of trying all combinations, we can use a sliding window technique to find the subarray of length n-k with the minimum sum.
   • The remaining elements (i.e., the elements not in the minimum subarray) will give us the maximum score.
   • Calculate the total sum of all card points.
   • Find the subarray of length n-k with the minimum sum using a sliding window.
   • The maximum score will be the total sum minus the minimum subarray sum.

4. Code Implementation (Optimal):

   def max_score(cardPoints, k):
       n = len(cardPoints)
       total_sum = sum(cardPoints)
       window_size = n - k
       current_sum = sum(cardPoints[:window_size])
       min_sum = current_sum
   
       for i in range(window_size, n):
           current_sum += cardPoints[i] - cardPoints[i - window_size]
           min_sum = min(min_sum, current_sum)
   
       return total_sum - min_sum
   

Big(O) Run-time Analysis:

• The optimal solution iterates through the cardPoints array once using a sliding window of size n-k, where n is the length of cardPoints and k is the number of cards to take.
• Therefore, the time complexity is O(n), where n is the number of cards.

Big(O) Space Usage Analysis:

• The optimal solution uses a constant amount of extra space to store variables such as total_sum, window_size, current_sum, and min_sum.
• Therefore, the space complexity is O(1), meaning the space required does not increase with the input size.

Edge Cases and Handling:

• k = 0: If k is 0, it means we don't have to pick any card, so the maximum score should be 0.
• k = n: If k is equal to the number of cards, we have to pick all of them. So the maximum score will be the sum of all card points.
• n = 1: If there is only 1 card, we simply return its value provided k = 1.

Handling them in code:

def max_score(cardPoints, k):
    n = len(cardPoints)
    if k == 0:
        return 0
    if k == n:
        return sum(cardPoints)

    total_sum = sum(cardPoints)
    window_size = n - k
    current_sum = sum(cardPoints[:window_size])
    min_sum = current_sum

    for i in range(window_size, n):
        current_sum += cardPoints[i] - cardPoints[i - window_size]
        min_sum = min(min_sum, current_sum)

    return total_sum - min_sum