tutorialcup@gmail.com

Find K length subarray of maximum average

Arrays
Reverse Array
Pair Sum Equals Number
Floor and Ceil
Largest Sum Subarray
Missing Number
Odd Occuring Number
Sort by Frequency
First and Second Smallest
Majority Element
Difference between elements
Arrange Even and Odd
Closest Sum Elements
Distinct Elements
First Repeating Number
Common Elements in Arrays
Smallest Missing Number
Max Adjacent Sum
Find Occurrences of Number
Rotate Image
Distance Between Numbers
Pair with given difference
Product Array Puzzle
Replace Elements
First Repeating Element
Move Zeroes to End
Pythagorean Triplets
Maximum Average Subarray
Subarray Sum Equal to X
Leaders in Array
Largest Pair Sum
Segregate 0s 1s and 2s
Find Duplicates
Consecutive Elements Check
Triplet with given Sum
Binary Search in Sorted Array
Fixed point in sorted array
Reorder Elements by Indexes
Merging two sorted arrays
Find next greater number
Reorder array using given indexes
Count of triplets with sum less than given value
Merge two sorted arrays
Subarray and Subsequence
Rearrange array maximum minimum form
Find the lost element from a duplicated array
Count minimum steps to get the given array
Maximum element in an array which is increasing and then decreasing
Minimum number of jumps to reach the end of an array
Subarray with given sum
Length of Longest Increasing Subsequence
Smallest positive number missing unsorted array
The Celebrity Problem
Sorted subsequence of size 3
Partition Problem
Find pair with given difference
Maximum length of chain pairs
Four elements that sum to given
Maximum circular subarray sum
Count possible triangles
Longest Increasing Subsequence
Petrol Bunks Tour
Tug of War
Counting Sort
Maximum Repeating Number
Positive Negative Arrangement
Find a Peak element
Elements More Than n/k
Max Product Subsequence
Longest Bitonic subarray in an array
Number of smaller elements on right side
Implement two stacks in an array
Maximum sum increasing subsequence
Find the two numbers with odd occurrences in an unsorted array
Largest subarray with equal number of 0's and 1's
Maximum product subarray
Replace every element with the greatest on the right side in an array
Sorting a k sorted array
Find the row with maximum number of 1's
Shuffle a given array
Iterative Implementation of quick sort
Arrange given numbers to form the biggest number
Pancake sorting
Pancake sorting Problem
Maximum Subarray Sum using Divide and Conquer
Merge Overlapping Intervals
Stock Buy Sell to Maximize Profit
Sort Elements by frequency
Print all possible combinations of r elements in a given array of size n
Monotonically increasing function
Minimum element in a sorted and rotated array
Merge k Sorted Arrays
Flip Zeroes for Consecutive 1's
Least Average Subarray
Longest span with same sum in two binary arrays
Form minimum number from given sequence of D's and I's
Number of strictly increasing subarrays
Minimum difference between any two elements in an array
Number of pairs with given sum
Make Array Palindrome
Dynamic Programming, Longest Bitonic SubSequence

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

 


C++ Online Test - Check Your Rank across the World


Next > < Prev
Scroll to Top