KETEKI2B editorial

editorial
,
1

PROBLEM LINK :

Practice
Contest

Setter: Abhilash

Tester: Harsh Raj

Editorialist: Harsh Raj

DIFFICULTY:

Easy

PREREQUISITES:

Partial Sum, Kadane's Algorithm

EXPLAINATION:

Store partial sum of the input array. Traverse the array,and 
for each subarray of size k, get the number of chips. For each
iteration, update the answer if number of chips in the 
subarray exceeds answer.

TIME COMPLEXITY:

O(N)

SOLUTIONS:

Settler's Solution 

	#include<bits/stdc++.h>
	#define ll long long
	using namespace std;
	main()
	{
	    int n,k;
	    cin>>n>>k;
	    ll a[n];
	    for(int i=0;i<n;i++)
	        cin>>a[i];
	    ll max_chips=0;
	    for(int i=0;i<k;i++)
	        max_chips+=a[i];
	    ll chips_in_hand=max_chips;
	    for(int i=k;i<n;i++){
	        chips_in_hand+=(a[i]-a[i-k]);
	        max_chips=max(max_chips,chips_in_hand);
	    }
	    cout<<max_chips<<"\n";
	}

Tester's Solution 

	#include <bits/stdc++.h>
	using namespace std;
	#define ll long long int
	 
	int main() {
		ll i,j,k,sum=0,n,m;
		cin>>n>>k;
		vector<ll> a(n);
	 
		for(i=0;i<n;i++)
			cin>>a[i];
		if(n < k){	//if there aren't k chips
			cout<<sum<<endl;
			return 0;
		}
	 
		for(i=1;i<n;i++)
			a[i]+=a[i-1];//storing partial sum
		sum=a[k-1];
		for(int index=k;index<n;index++)
			sum=max(sum,a[index]-a[index-k]);
		
		cout<<sum<<endl;
	  	
	  return 0;
	}