I am trying to solve this problem I posted earlier: https://stackoverflow.com/questions/78270434/calculate-maximum-points-earned/78270606
Example There are n = 3 sprints, the number of days of each sprint are days = [2,3,2], and k=4.
The maximum number of points that can be attained = 2+1+2+3 = 8.
One choice is to start on the last day of the first sprint and end on the last day of the second sprint.
Here is my brute force approach, that check each index as starting to get the maximum points.
static long solve(int[] arr, int k) {
long maxPoints = 0;
int n = arr.length;
for (int i = 0; i < n; i++) {
int index = i;
long currentPoints = 0;
int k1 = k;
while (k1 > 0) {
for (int j = arr[index]; j > 0 && k1 > 0; j--, k1--) {
currentPoints += j;
}
index++;
if (index == n) {
index = 0;
}
}
maxPoints = Math.max(maxPoints, currentPoints);
}
return maxPoints;
}
This code runs with time complexity of O(n * k) where n is size of input array. I am looking for better approach that takes less time complexity.
First iterate over the array and calculate the sum and the score, the score is the sum of arr[i] * (arr[i] + 1) / 2. Then you set total score to k / sum * score (integer division) and k = k % sum. k is now in the range 0 to sum - 1, this makes it easier and it is important if k is a lot bigger than sum. In the end you return total + bestScore and bestScore is the best scoring sliding window of size k (the new k, if it is 0 you can return total right away).
After this normalization you can go over the array using a sliding window. A simple approach would take O(sum(arr)), which is still better than brute-force O(k*sum(arr)) but not impressive. The key is to see that as long as the start and end of the window are not changing their sprint the score keeps changing at a constant rate (this is because the score of the day dropping out of the window is always increased by 1 as long as we are in the same sprint and the same is true for the day coming into the window), so we can jump directly to the end of the sooner ending sprint and move the sliding window in bigger steps than just one day at a time. The rate of change is the difference between the days of the window boundaries, add it as many times to the current score as you go days ahead then compare with best and repeat until the start of the window reaches the end of the array (the end of the window wraps around).
This leads to a O(n) solution independent of k with O(1) storage.
public static long sumUp(int n) {
return n * (n + 1L) / 2L;
}
public static long solve(int[] arr, int k) {
// ***** normalize *****
long sum = 0, score = 0;
for (int a : arr) {
sum += a;
score += sumUp(a);
}
long baseScore = k / sum * score;
k = (int) (k % sum);
if (k == 0) return baseScore;
// ***** prepare sliding window *****
int startSprint = 0, startDay = 0, endSprint = 0, endDay = 0;
long currScore = 0;
while (k >= arr[endSprint]) {
currScore += sumUp(arr[endSprint]);
k -= arr[endSprint++];
}
currScore += sumUp(k);
endDay = k; // exclusive
long bestScore = currScore;
// ***** slide the window *****
while (startSprint < arr.length) {
int startDaysLeft = arr[startSprint] - startDay;
int endDaysLeft = arr[endSprint] - endDay;
int change = endDay - startDay;
if (startDaysLeft == endDaysLeft) {
currScore += change * startDaysLeft;
startDay = 0;
endDay = 0;
startSprint++;
endSprint = (endSprint + 1) % arr.length;
} else if (startDaysLeft < endDaysLeft) {
currScore += change * startDaysLeft;
startDay = 0;
endDay += startDaysLeft;
startSprint++;
} else {
currScore += change * endDaysLeft;
startDay += endDaysLeft;
endDay = 0;
endSprint = (endSprint + 1) % arr.length;
}
if (currScore > bestScore) bestScore = currScore;
}
return baseScore + bestScore;
}