Maximum Fixed-Length Sum
National Olympiad — Municipal round
Submission name: maxk.cpp
Problem summary
Find the greatest sum of exactly k consecutive entries of an integer sequence. Negative entries are allowed.
Input
n k, then n integers.
Output
The maximum segment sum.
Constraints
1 ≤ k ≤ n ≤ 1000; −9999 ≤ a[i] ≤ 9999.
Worked example
An independently prepared example for this explanation.
Input
5 2 -4 -2 -8 -1 -3
Output
-4
Solution analysis
- Sum the first k values.
- Slide the window by subtracting the departing entry and adding the entering entry.
- Keep the largest window sum.
Why it works
Each update preserves exactly the current k-entry sum. Every possible window is examined.
Complexity: O(n) time, O(n) storage.
Watch out. Initialize from the first window, not zero: all sums may be negative.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<limits>
#include<numeric>
#include<set>
#include<map>
#include<tuple>
#include<cstdint>
#include<functional>
#include<cmath>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
vector<int>a(n);
for(int&x:a){
cin>>x;
}
int sum=accumulate(a.begin(),a.begin()+k,0),best=sum;
for(int i=k;i<n;i++){
sum+=a[i]-a[i-k];
best=max(best,sum);
} // One window update.
cout<<best<<'\n';
}