medium Maximum Points You Can Obtain from Cards

Problem Statement

You are given several cards arranged in a single row, where i^th card has cardPoints[i] points.

In a single step, you can take one card from the start or from the end of the row. You have to take exactly k cards.

The score is the sum of the points of the cards you have withdrawn.

Given the cardPoints array containing integers and the integer k, return the maximum score you can obtain.

Examples

• Example 1:

  • Input: cardPoints = [10, 14, 7, 2, 8, 9, 4], k = 3
  • Expected Output: 31
  • Justification: The best strategy is to take the cards with 10, 14, and 7 points. The maximum score will be 10 + 14 + 7 = 31.

• Example 2:

  • Input: cardPoints = [1, 2, 3, 4, 5, 6], k = 2
  • Expected Output: 11
  • Justification: Taking the two cards from the right end (5 and 6) gives us the highest score. The sum here is higher than any other combination of 2 cards.

• Example 3:

  • Input: cardPoints = [91, 24, 36, 48, 72, 19, 29], k = 4
  • Expected Output: 211
  • Justification: The optimal move is to take 91 from the left, then 29, 19, and 72 from the right, achieving the maximum possible score.

Solution

To solve this problem, the intuitive approach might be to try all possible combinations of picking cards from both ends. However, this approach is not feasible due to its high computational complexity. Instead, a more efficient strategy involves focusing on the sub-array of cards that we will not select. If we can minimize the total points of the cards not chosen, we effectively maximize the points from the cards we do select. This approach is both time-efficient and logically sound because it flips the problem on its head by concentrating on what we leave behind rather than what we take.

The essence of this strategy is to use a sliding window technique to identify the sub-array of length n-k (where n is the total number of cards and k is the number of cards to select) that has the minimum sum. This sub-array represents the cards we will not take. By subtracting this sum from the total points available, we obtain the maximum points we can score. This method is efficient and sidesteps the need for exhaustive search, making it a practical solution for the problem at hand.

Step-by-step Algorithm

1. Initialize Variables:

   • Calculate the totalSum of all card points in the array.
   • Determine the number of cards n.
   • Calculate the size of the window as windowSize = n - k. This window represents the cards that are not selected.
   • Set currentSum to the sum of the first windowSize elements in the array.
   • Initialize minSubArraySum with the value of currentSum.

2. Find the Minimum Sum Sub-array:

   • Starting from index windowSize, iterate through the cardPoints array.
   • For each position, adjust currentSum by subtracting the element at the start of the window and adding the current element (this effectively slides the window one position to the right).
   • Update minSubArraySum if the new currentSum is less than the current minSubArraySum.

3. Calculate Maximum Score:

   • The maximum score is calculated as maxScore = totalSum - minSubArraySum. This is because the minimum sum of the non-selected cards subtracted from the total sum gives the maximum possible sum of the selected cards.

4. Return maxScore as the result.

Algorithm Walkthrough

Given the input [91, 24, 36, 48, 72, 19, 29], k = 4.

1. Initialize Variables:

   • totalSum = 91 + 24 + 36 + 48 + 72 + 19 + 29 = 319
   • n = 7
   • windowSize = n - k = 7 - 4 = 3
   • currentSum = 91 + 24 + 36 = 151
   • minSubArraySum = 151

2. First Window: (already calculated)

   • window = [91, 24, 36]
   • currentSum = 151
   • minSubArraySum = 151

3. Slide the Window:

   • Slide 1:
     • Remove 91 (start of the window), add 48 (new end of the window).
     • currentSum = 151 - 91 + 48 = 108
     • minSubArraySum = 108 (updated because 108 < 151)
   • Slide 2:
     • Remove 24, add 72.
     • currentSum = 108 - 24 + 72 = 156
     • minSubArraySum remains 108 (since 156 > 108)
   • Slide 3:
     • Remove 36, add 19.
     • currentSum = 156 - 36 + 19 = 139
     • minSubArraySum remains 108 (since 139 > 108)
   • Slide 4:
     • Remove 48, add 29.
     • currentSum = 139 - 48 + 29 = 120
     • minSubArraySum remains 108 (since 120 > 108)

4. Calculate Maximum Score:

   • maxScore = totalSum - minSubArraySum = 319 - 108 = 211

5. Result:

   • The maximum score that can be obtained is 211.

Code

public class Solution {

  // Function to find the maximum score
  public int maxScore(int[] cardPoints, int k) {
    int totalSum = 0;
    for (int point : cardPoints) {
      totalSum += point; // Calculate total sum of all points
    }
    int n = cardPoints.length;
    int windowSize = n - k; // Calculate the size of the window (cards not to be selected)
    int currentSum = 0;
    for (int i = 0; i < windowSize; i++) {
      currentSum += cardPoints[i]; // Initial sum of the first window
    }
    int minSubArraySum = currentSum; // Initialize minimum sum with the first window's sum
    for (int i = windowSize; i < n; i++) {
      currentSum += cardPoints[i] - cardPoints[i - windowSize]; // Slide the window and update sum
      minSubArraySum = Math.min(minSubArraySum, currentSum); // Update minimum sum found
    }
    return totalSum - minSubArraySum; // Subtract minimum sub-array sum from total to get maximum score
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    System.out.println(
      solution.maxScore(new int[] { 10, 14, 7, 2, 8, 9, 4 }, 3)
    ); // Expected output: 31
    // Example 2
    System.out.println(solution.maxScore(new int[] { 1, 2, 3, 4, 5, 6 }, 2)); // Expected output: 11
    // Example 3
    System.out.println(
      solution.maxScore(new int[] { 91, 24, 36, 48, 72, 19, 29 }, 4)
    ); // Expected output: 211
  }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm is , where n is the length of the cardPoints array. This efficiency is achieved because the algorithm iterates over the array only once to calculate the total sum and then performs a single pass with a sliding window to find the minimum sum of the sub-array of size n-k. The operations within each iteration are constant time operations, leading to a linear time complexity.

Space Complexity

The space complexity of the algorithm is . This is because the algorithm uses a fixed amount of extra space regardless of the input size.