Collecting Jewels
InterviewTime limit2sMemory limit128 MB
Given N values in a line, find the maximum sum of a single contiguous run of length at least M taken once.
- Level
Medium4 of 10
- Topics
- Prefix sum, Dynamic programming, Sliding window
- Solved
- No attempts yet
Problem
Hwayoung walks past N jewels arranged in a line, from jewel 1 to jewel N. Each jewel has a value, and some values may be negative.
Because traps are placed between the jewels, Hwayoung cannot go back after passing a position. At each position, she either takes that jewel or leaves it and moves to the next position.
Because of the alarm system, once Hwayoung starts taking jewels, she must take at least M consecutive jewels, including the jewel where she started. After she stops taking jewels, she cannot take any more jewels and must leave the ruins immediately.
Find the maximum possible total value of the jewels she can take while satisfying these conditions.
Input
The first line contains two integers N and M.
Each of the next N lines contains the value of one jewel, in order from jewel 1 to jewel N.
1 ≤ M ≤ N ≤ 100,000, and the absolute value of each jewel value is at most 2,000.
Output
Print the maximum possible total value of the jewels that can be taken while satisfying the conditions.