Challenge: Best k Days

Lab C++ Beginner 10 points

Read daily step counts and k. Print the largest total of any k days in a row using a sliding window.

Input

Line 1: n k. Line 2: n whole numbers.

Output

The best total.

Example

Input

6 3
2 1 5 1 3 2

Output

Sample input available Sample output available

Editor

C++

Hints

Add up the first k numbers.

Slide: window += v[r] - v[r - k].

Solution explanation

O(n) no matter how big k is.

Show solution

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> v(n);
    for (auto& x : v) cin >> x;
    long long window = 0;
    for (int i = 0; i < k; i++) window += v[i];
    long long best = window;
    for (int r = k; r < n; r++) {
        window += v[r] - v[r - k];
        best = max(best, window);
    }
    cout << best << endl;
    return 0;
}

Output

Answer