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.
1public int maxScore(int[] cardPoints, int k) {
2 int n = cardPoints.length;
3 int totalSum = 0;
4 for (int point : cardPoints) totalSum += point;
5 int windowSize = n - k;
6 int minUnusedSum = Integer.MAX_VALUE;
7 int currentWindowSum = 0;
8 for (int i = 0; i < n; i++) {
9 currentWindowSum += cardPoints[i];
10 if (i >= windowSize) {
11 currentWindowSum -= cardPoints[i - windowSize];
12 }
13 if (i >= windowSize - 1) {
14 minUnusedSum = Math.min(minUnusedSum, currentWindowSum);
15 }
16 }
17 return totalSum - minUnusedSum;
18}
19
20// Example Usage
21// Output: 12This Java solution was implemented similar to the Python solution. A comprehensive loop is used to find the subarray with minimal sum using a moving sum updated within the loop to ensure efficiency. Total sum minus this minimum gives the maximum points that can be taken.
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.
1#include <vector>
2#include <algorithm>
3
4int maxScore(std::vector<int>& cardPoints, int k) {
int n = cardPoints.size();
std::vector<int> prefix(k + 1, 0);
std::vector<int> suffix(k + 1, 0);
for (int i = 0; i < k; i++) {
prefix[i + 1] = prefix[i] + cardPoints[i];
suffix[i + 1] = suffix[i] + cardPoints[n - i - 1];
}
int max_points = 0;
for (int i = 0; i <= k; i++) {
max_points = std::max(max_points, prefix[i] + suffix[k - i]);
}
return max_points;
}
// Example Usage
// Output: 12The C++ solution involves initiating prefix and suffix arrays that hold summed values progressively such that each index i in either array holds the sum of the first i or last i elements of the main array. Then a loop is used to check each possible distribution of cards between prefix and suffix to find and combine the maximum scores achievable with k moves.