Problem

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.

Examples

Example 1:

1
2
3

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:

1
2
3

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:

1
2
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.

Solution

Method 1 - Brute Force

We can take x cards from starting and k-x card from the end. This means we iterate x from 0 to k. Time complexity wil be O(k*k-x) = O(k^2) We can loop from left to right till k and remaining sum from right to left till k-x.

Method 2 - Sliding Window

We can use inversion here. Instead of finding max elements on the sides, we can find the smallest subarray sum of length len(cardPoints) - k. Then the remaining k element sum will be max.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

public int maxScore(int[] cardPoints, int k) {
	int n = cardPoints.length;
	int minSubarrayLength = n - k;
	int minSum = Integer.MAX_VALUE, currentSum = 0, totalSum = 0;
	for (int r = 0, l = 0; r < n; r++) {
		totalSum += cardPoints[r];
		currentSum += cardPoints[r];
		if (r - l + 1 == minSubarrayLength) {
			minSum = Math.min(minSum, currentSum);
			currentSum -= cardPoints[l];
			l++;
		}
	}
	return totalSum - (minSum == Integer.MAX_VALUE ? 0 : minSum);
}

Method 3 - Using Prefix Sum

When taking a card from either left or right k times, there will have 3 cases:

  1. All selected cards from the left.
  2. All selected cards from the right.
  3. Selected cards taken from both sides. Why not create sum with first k elements on the left. Now, we can iterate from end to see if our current end sum is max or not.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public int maxScore(int[] cardPoints, int k) {
    int n = cardPoints.length;
    int leftsum = 0;
    for (int i = 0; i < k; i++) {
        leftsum += cardPoints[i];
    }
    int max = leftsum;
    int rightsum = 0;

    for (int i = 0; i < k; i++) {
        leftsum  -= cp[k - 1 - i];
        rightsum += cp[n - 1 - i];
        max = Math.max(max, leftsum + rightsum);
    }

    return max;
}

Complexity

  • ⏰ Time complexity: O(n), worst when k = n, all cards are counted.
  • 🧺 Space complexity: O(1)