How to find sum of all subarrays of size k

1

Can we find the sum of all subarray of size k in efficient way??

if A = [1,2,3,4,6] and k = 3, then op will be 6,9,13
(6=1+2+3,9=2+3+4,13=3+4+6)

2

please help someone…

3

bro you can read this article you have to do the same just here we are finding maximum sum of subarray of size k and in your case we have to find sum of all subarray of size k :- :Find maximum (or minimum) sum of a subarray of size k - GeeksforGeeks

here is code ,algorithm used is sliding window :

#include<iostream>
using namespace std;

int main()
{
	long long n,k;            //size of array and size of required subarray
	cin>>n>>k;
	
	
	long long A[n],i,j,sum=0,tot=0;
	for(i=0;i<n;++i)
	{
		cin>>A[i];         //taking array inputs
	}
	
	//finding sum of first k elemets 
	
	for(i=0;i<k;++i)
	{
		sum+=A[i];       //we are storing sum of first subarray of length k
	}
	
	tot+=sum;         //storing sum of all subarray in tot variable 
	
	//we will loop from k to n and find sum of all remaining subarray sum
	
	for(i=k;i<n;++i)
	{
		sum+=A[i];              //example array is 1,2,3,4,5 , we found sum upto 4  here length k=3
		sum-=A[i-k];            //we subtract the value of 1st elemnt to get sum of subarray 2,3,and 4
		 
		tot+=sum;             //finally storing value of sum in tot
	}
	
	cout<<tot<<endl;
	
	
}```
1 Like
4

I think you can use a sliding window approach here. Start at index 0 and make a window of size k, adding the elements. so for a windows of size k, you have i=0 and j=k-1. Now when you try to move the window ahead by one, you’ll notice the size exceeds k. So you first need to remove the last element and then add the next element. i.e i=1 and j=k. this way by moving the window across the entire array, you can get sums of all subarrays of size k

1 Like
5

Google for sliding window approach

1 Like