A long ridge trail has n numbered rest points laid out in a straight line, indexed 0 through n-1. Rest point i carries a scenic score score[i] (a positive score rewards a nice view, a negative score marks a rough patch). A hiker wants to log an ordered sequence of checkpoints i_1 < i_2 < ... < i_m (m >= 1, chosen from the n rest points) in her trail journal. Two rules govern a valid sequence: consecutive chosen checkpoints must be at least k rest points apart, i.e. i_{t+1} - i_t >= k for every t, and the journal entry alternates in sign — the score of the 1st, 3rd, 5th, ... chosen checkpoint is added, while the score of the 2nd, 4th, 6th, ... chosen checkpoint is subtracted. The hiker's logged total for a sequence is score[i_1] - score[i_2] + score[i_3] - score[i_4] + .... Help her pick a valid sequence (she may log just a single checkpoint) that maximizes this logged total.
The first line contains two integers n and k. The second line contains n integers score[0], score[1], ..., score[n-1].
Print a single integer: the maximum logged total achievable over all valid checkpoint sequences.
Example 1
Input
3 1 10 -20 10
Expected
40
Explanation
The hiker logs all three checkpoints (each consecutive pair is 1 apart, satisfying k=1): 10 - (-20) + 10 = 40. No other valid sequence beats this.
Example 2
Input
5 2 1 -50 8 -50 9
Expected
51
Explanation
Logging checkpoints 0 and 3 (3 apart, satisfying k=2) gives score[0] - score[3] = 1 - (-50) = 51. This beats every alternative: checkpoint 4 alone scores only 9, and combining checkpoints 0 and 2 gives 1 - 8 = -7.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →