Busiest sales days
A shop records daily item sales. Given window width W and N daily totals, find the consecutive W-day window with the greatest sum. Print its zero-based starting day and total. When multiple windows tie, keep the earliest. The input may include zero-sale days.
Input
First line N and W; second line N non-negative integer daily totals. 1 <= W <= N <= 1000.
Output
start total for the earliest maximum window.
Example 1
Input
6 3 2 5 1 4 2 1
Output
1 10
The window starting at day 1 contains 5, 1 and 4, totaling 10; every other three-day window is lower.
Constraints
- 1 <= W <= N <= 1000.
- Daily sales are non-negative integers of at most 1000000.
Hints
Hint 1 of 2
Subtract the day leaving the window and add the entering day.
Hint 2 of 2
Updating only for a strictly greater sum preserves the earliest tie.
Solution
Show a reference solution and explanation
n, width = map(int, input().split())
values = list(map(int, input().split()))
current = sum(values[:width])
best = current
start = 0
for i in range(width, n):
current += values[i] - values[i - width]
if current > best:
best = current
start = i - width + 1
print(start, best)
Why it works
Initialize the first W-day sum, then slide in O(1) time per day by adding the new value and subtracting the expired one. Compare only after each complete window. A strict greater-than update preserves the first window when totals tie; total time is O(N).
Lesson for this exercise: Lists in Python