Sponsored
Sponsored
The 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.
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.
1def maxScore(cardPoints, k):
2 n = len(cardPoints)
3 total_sum = sum(cardPoints)
4 window_size = n - k
5 min_unused_sum = float('inf')
6 current_window_sum = 0
7 for i in range(n):
8 current_window_sum += cardPoints[i]
9 if i >= window_size:
10 current_window_sum -= cardPoints[i - window_size]
11 if i >= window_size - 1:
12 min_unused_sum = min(min_unused_sum, current_window_sum)
13 return total_sum - min_unused_sum
14
15# Example Usage
16print(maxScore([1,2,3,4,5,6,1], 3)) # Output: 12The 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.
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.
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.
1public int MaxScore(int[] cardPoints, int k) {
2 int n = cardPoints.Length;
3 int[] prefix = new int[k + 1];
4 int[] suffix = new int[k + 1];
for (int i = 0; i < k; i++) {
prefix[i + 1] = prefix[i] + cardPoints[i];
suffix[i + 1] = suffix[i] + cardPoints[n - i - 1];
}
int maxPoints = 0;
for (int i = 0; i <= k; i++) {
maxPoints = Math.Max(maxPoints, prefix[i] + suffix[k - i]);
}
return maxPoints;
}
// Example Usage
// Output: 12The C# approach utilizes prefix and suffix accumulators to compute possible scores based on the card distribution across k moves. Looping over possible scenarios enables determination of the best option to yield a maximum score based on k selections.