Skip to content
MediumArraysNot started

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
 Python · reference solution
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)

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.

Your program
count, size = map(int, input().split())
parcels = list(map(int, input().split()))
# find the best window

Tests: 4 cases including the examples. Run here in Python, JavaScript.

How this page was checked. Reference solutions were checked by the publishing checks. The selector offers only languages runnable in your browser; other reference code is for local use.