Temperature Sequence

Interview

Time limit1sMemory limit128 MB

Summary

Find the maximum sum of any K consecutive elements in an array of N temperatures.

Level: Easy3 of 10
Topics: Sliding window, Prefix sum, Array
Solved: No attempts yet

Problem

A sequence of daily temperatures is given. For a fixed number K, find the largest possible sum of temperatures over any K consecutive days.

Write a program that computes this maximum K-day sum.

Input

The first line contains two integers N and K separated by a space.

N is the number of measured days, with 2 <= N <= 100,000.
K is the number of consecutive days to sum, with 1 <= K <= N.

The second line contains N integers separated by spaces. Each integer is a daily temperature, and every temperature is between -100 and 100 inclusive.

Output

Print the maximum sum among all consecutive K-day temperature sums.

Examples2

Example 1
Input
```
10 2
3 -2 -4 -9 0 3 7 13 8 -3
```
Expected output
```
21
```
Example 2
Input
```
10 5
3 -2 -4 -9 0 3 7 13 8 -3
```
Expected output
```
31
```