Find the largest sum of k numbers that stand next to each other in the array. Use a sliding window: O(n), not O(n × k).
Input
The first line has n and k (1 ≤ k ≤ n ≤ 10,000). The second line has the n numbers (each from -10,000 to 10,000).
Output
The largest sum of k consecutive numbers.
Examples
Example 1 · Input
6 3 2 1 5 1 3 2
Expected output
9
Example 2 · Input
4 4 -1 -2 -3 -4
Expected output
-10
Hints
Hint 1
Add up the first k numbers.
Hint 2
Slide: add a[i] and subtract a[i - k], keeping the largest sum seen.
Hint 3
Numbers can be negative, so start best with the first window's sum, not 0.
Solution
Show one correct solution (try it yourself first)
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (auto& x : a) cin >> x;
long long sum = 0;
for (int i = 0; i < k; i++) sum += a[i];
long long best = sum;
for (int i = k; i < n; i++) {
sum += a[i] - a[i - k];
if (sum > best) best = sum;
}
cout << best << "\n";
return 0;
}