Find the busiest packing window
A warehouse records the number of parcels packed in each shift. For a window of K consecutive shifts, print the largest parcel total and the one-based shift where that window begins. If several windows have the same total, choose the earliest.
Input
First line: N and K. Second line: N non-negative integer parcel counts.
Output
Two integers: the largest window total and its one-based starting shift.
Example 1
Input
7 3 4 8 2 9 6 1 5
Output
19 2
Shifts 2 through 4 contain 8 + 2 + 9 = 19 parcels, the largest total.
Constraints
- 1 <= K <= N <= 100000
- 0 <= parcels per shift <= 10000
Hints
Hint 1 of 3
First compute the total of shifts 1 through K.
Hint 2 of 3
Move the window one shift by subtracting the count that leaves and adding the count that enters.
Hint 3 of 3
Update the answer only for a strictly larger total so a tie keeps the earlier start.
Solution
Show a reference solution and explanation
count, size = map(int, input().split())
parcels = list(map(int, input().split()))
current = sum(parcels[:size])
best = current
best_start = 0
for right in range(size, count):
current += parcels[right] - parcels[right - size]
if current > best:
best = current
best_start = right - size + 1
print(best, best_start + 1)
const [count, size] = readline().split(' ').map(Number);
const parcels = readline().split(' ').map(Number);
let current = parcels.slice(0, size).reduce((sum, value) => sum + value, 0);
let best = current;
let bestStart = 0;
for (let right = size; right < count; right++) {
current += parcels[right] - parcels[right - size];
if (current > best) { best = current; bestStart = right - size + 1; }
}
console.log(best, bestStart + 1);
Approach
The first window is summed once. Each later window reuses that total, removing its leftmost value and adding the new rightmost value. This makes the scan linear, and the strict comparison preserves the earliest position when totals tie.