PROBLEM LINK:
Author: Sandeep Singh
Tester: Md. Shahid
Editorialist: Sandeep Singh
DIFFICULTY:
EASY
PREREQUISITES:
Knowledge of window sliding might be helpful
EXPLANATION:
The problem is a standard implementation of sliding window in a circular array. We take the sum of the first K elements, that is our window,. Then we move the window towards right till the start of the window reaches the end. After that, all windows will be repeating. so we stop. While doing this we store the max sum of window during the entire process.
For more details on:
window sliding .
Using this technique on cirular array
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long int
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define scanarr(a,b,c) for( i=b;i<c;i++)cin>>a[i]
#define showarr(a,b,c) for( i=b;i<c;i++)cout<<a[i]<<' '
#define ln cout<<'\n'
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
#define MAX 100005
using namespace std;
////////////////////////////////////////////////////////////////CODE STARTS HERE////////////////////////////////////////////////////////////////
void solve(){
int n, k;
int i, j;
cin >> n >> k;
int arr[n];
for(i=0;i<n;i++)
cin>>arr[i];
ll sum = 0;
for(i=0;i<k;i++)
sum+=arr[i];
ll ans = sum;
for(i=1;i<n;i++){
sum -= arr[i-1];
sum += arr[(i+ k -1)%n];
ans = max(sum,ans);
}
cout<< ans<<endl;
}
int main(){
FAST
#ifndef ONLINE_JUDGE
freopen("ip4.in","r",stdin);
freopen("op4.out","w",stdout);
#endif
int t;
cin>>t;
while(t--)
solve();
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long int
#define ll long long int
#define vi vector<int>
#define vvi vector<vector<int>>
#define pll pair<ll, ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vpll vector<pair<ll,ll>>
#define umap unordered_map
#define uset unordered_set
#define all(c) c.begin(), c.end()
#define maxarr(A) *max_element(A, A+n)
#define maxvec(v) *max_element(all(v))
#define present(map,elem) map.find(elem)!=map.end()
#define lb(v,elem) lower_bound(all(v),elem)
#define ub(v,elem) upper_bound(all(v),elem)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define For(i,a,b) for(int i=a; i<b; ++i)
#define rep(i,a,b) for(ll i=a; i<b; ++i)
#define debug(v) for(ll i=0; i<v.size(); i++) cout<<v[i]<<" "; cout<<endl;
#define debugn(v,n) for(ll i=0; i<n; i++) cout<<v[i]<<" "; cout<<endl;
#define mod 1000000007
#define endl '\n'
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("1.in","r",stdin);
int t;
cin>>t;
//assert(t<=10);
while(t--){
ll n,k;
cin>>n>>k;
// assert(n<=100000 && n>=5);
// assert(k>=1 && k<=n/2);
vl a(n);
for(ll i=0; i<n; i++) cin>>a[i];
ll j=0;
ll ans=0,sm=0;
for(ll i=0; i<k; i++){
sm += a[i];
}
ans = sm;
for(ll i=k; i<n+k; i++){
sm += a[i%n];
sm -= a[j];
j++;
// cout<<sm<<endl;
ans = max(ans,sm);
}
cout<<ans<<endl;
}
return 0;
}