Loading...
Loading...
Loading...
A shop records its daily profit for n days. A loss is written as a negative number. The owner wants to advertise the best stretch of exactly k consecutive days.
Print the largest total profit of any k consecutive days.
Example 1
Input
6 3 2 1 5 1 3 2
Output
9
Days 2–4 give 1 + 5 + 1 = 7, but days 3–5 give 5 + 1 + 3 = 9.
Example 2
Input
4 2 -5 -2 -8 -1
Output
-7
Every total is negative. The best is −5 + −2 = −7.
Try the problem first. Open one hint at a time.
Adding up every window from scratch costs O(n × k), which is too slow when both are large.
Slide the window: add the day that enters on the right, subtract the day that leaves on the left.
Start best with the first window's total, not with 0. Every total may be negative.
A window total can reach 10^5 × 10^9 = 10^14, so keep totals in a long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor