Find K length subarray of maximum average

Finding the start position of subarray in the given array of size k with maximum average

Array may contain positive and negative numbers. (Average = sum of elements/number of elements). Sub arrays are subsets of an array.

Examples of sub array

For array [1, 3, 4, 5, 7, 8, -10, -11]
    [1, 3, 4] is a sub array of size 3
    [5, 8, -10] is not a sub array
    [-11, -10, 8] is not a sub array
    [7, 8, -10, -11] is a sub array of size 4

Example:

Input array

Find the sub array of size 3 with maximum average ?

Sub arrays of size 3 in the given array are

Sum of elements = 11, Average = 11/3

Sum of elements = 5, Average = 5/3

Sum of elements = 3, Average = 3/3

Sum of elements = 21, Average = 21/3

Therefore, sub array of size 3 with maximum average is

Method 1

Time complexity:O(n*k),

where n is size of array and k is subarray size.

Algorithm

Step 1 : If k > n, it prints “No such subarray with that size possible”. Because, there can`t be an array with size more than its size.

Step 2 : We initialize sum_here = 0, max_sum = INT_MIN

Step 3 : We find sum of elements in all the subarrays of size k and compare with max_sum and if max_sum<sum_here we update max_sum. We do this for all the subarrays.

a.    We run two loops to find the sum of subarrays, from 0 to N-K (first loop) from 0 to K-1 (second loop).In second loop we add all the elements to sum here to find the sum of all the subarrays of size k.
b.    If max_sum<sum_here we update. We also update the pos_max which the start position of the subarray.

Step 4 :  We print the pos_max which is start of subarray of maximum average.

Algorithm Working Example

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int arr[] ={ 1, 12, -5, -6, 50, 3}; //array
	int N = sizeof(arr)/sizeof(arr[0]); //size of array
	int K;
	cin>>K;
	
	if(K > N)
		{
			cout <<"No such subarray with that size possible\n";
			return -1;	
		}	
	
	int max_sum = INT_MIN; //to store the maximum sum of such subarray with size K
	int sum_here = 0,pos_max; //maximum sum and starting position of such subarray respectively
	
	for(int i=0; i <=N-K;i++)
	{
		for(int j =0; j<K; j++)
			sum_here += arr[i+j];
			
		if(sum_here > max_sum)
		{
			max_sum = sum_here;
			pos_max = i;
		}
	}
	
	cout<<"Maximum average subarray starts from index "<<pos_max;
}
Try It

Method 2

Algorithm

Time complexity :  O(n)
Space complexity : O(n)

In this algorithm, we are taking the sum of first k elements and making it as maximum sum, and traversing the array such that we add next element of subarray to sum and subtracting the first element to the subarray sum which makes sum of new subarray.
compare with the maximum sum and if maximum sum is less thanthe new subarray sum then update maximum sum and store the start position of the subarray. continue this till the end of array.

Step 1 : First we compute the sum of the first subarray of size k and store it in sum_here and update the maximum sum to sum_here.

a.    Initialize max_sum to minimum value of integer, such that no other is smaller than that. (Using INT_MIN)
b.    Update max_sum to sum of the first k elements, using max function. (max(A,B))

Step 2 : Now we traverse the array by subtracting the first element and adding the present element.

a.    Initialize the value of index to K
b.    Here, we take index and increment it until N and for every value of index we find the sum_here that is adding the present index element and subtracting the first element.

c.    We do this until index is less than N

Step 3 : We compare the sum_here at every index value with max_sum to find the maximum sum. we update the max_sum and we get the position.

a.    We compare sum_here with max_sum and if sum_here is greater than max_sum. We update max_sum to sum_here. We will get the max_sum of the subarray of the given length.
b.    We get the position that is the starting index of the max sub -array by doing index – K + 1. We get the position.

Algorithm working Example

To find maximum average subarray of size 2 in given array.

Start :
Sum_here = = 4 + 7 = 11
Therefore, here max_sum = 11.
We initialize index = 2, till index < 5 we compare sum_here with max_sum

For index = 2.
Sum_here = 11 – 4 + (-6) = 1
1 >11  -> False

For index = 3.
Sum_here = 1 – 7 + 8 = 2
2 >1  -> True
    Therefore, max_sum = 2 and subarray position = 2.

For index = 4.
Sum_here = 2 + 13 + 6 = 21
21 >2  -> True
    Therefore, max_sum = 21 and subarray position = 3.

End.
Prints max_sum = 21 and subarray start position is = 3.
Therefore,
maximum subarray of size 2 starts from position 3.

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int arr[] ={ 1, 12, -5, -6, 50, 3}; //array
	int N = sizeof(arr)/sizeof(arr[0]); //size of array
	int K;
	cin>>K;
	
	if(K > N)
		{
			cout <<"No such subarray with that size possible\n";
			return -1;	
		}	
	
	int max_sum = INT_MIN; //to store the maximum sum of such subarray with size K
	int sum_here = 0;
	for(int i = 0; i < K; i++)
		sum_here += arr[i]; //compute sum of the first subarray with size K
		
	max_sum = max(max_sum,sum_here); //update the maximum sum
	
	int index = K,pos_max = 0; //index from where to traverse and pos_max is the starting position of such subarray
	
	while(index < N) //traverse the left array by eliminating the first element from sum and adding the current element and updating maximum sum accordingly
	{
		sum_here = sum_here - arr[index - K] + arr[index];
		if(sum_here > max_sum) //if we get a larger sum of subarray then update both maximum sum and starting index of such subarray
		{
			max_sum = sum_here;
			pos_max = index - K +1;//starting index of subarray
		}
	index++;
	}
	
	cout<<"Maximum average subarray starts from index "<<pos_max;
}
Try It

 


Next > < Prev
Scroll to Top