# Find K Length Subarray of Maximum Average

Difficulty Level Easy
ArrayViews 505

## Problem Statement

In find K length subarray of maximum average problem, we have given an array of size N. Finding the start position of a subarray in the given array of size k with a maximum average. The array may contain positive and negative numbers. (Average = sum of elements/number of elements). Sub arrays are subsets of an array.

## Example

Input

8 3

[1, 3, 4, 5, 7, 8, -10, -11]

Output

3

Explanation

Here maximum average subarray sum is 5+7+8 = 20/3 which starts from index 3.

## Approach 1

### 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 the 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 the 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 the start of the subarray of the maximum average.

### Implementation

#### C++ Program for Find K Length Subarray of Maximum Average

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int N,K;
cin>>N>>K;
int arr[N];
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
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++)
{
sum_here=0;
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;
}```

#### Java Program for Find K Length Subarray of Maximum Average

```import java.util.Scanner;

class sum
{
public static int main(String[] args)
{
Scanner sr = new Scanner(System.in);
int N = sr.nextInt();
int K = sr.nextInt();
int arr[] = new int[N];
for(int i=0;i<N;i++)
{
arr[i] = sr.nextInt();
}
if(K>N)
{
System.out.println("No such subarray with that size possible");
return -1;
}
int max_sum=-1; //to store the maximum sum of such subarray with size K
int sum_here=0, pos_max = 0; //maximum sum and starting position of such subarray respectively
for(int i=0; i<=N-K;i++)
{
sum_here=0;
for(int j =0; j<K; j++)
sum_here += arr[i+j];

if(sum_here > max_sum)
{
max_sum = sum_here;
pos_max = i;
}
}
System.out.println("Maximum average subarray starts from index " + pos_max);
return 0;
}
}```
```8 3
1 3 4 5 7 8 -10 -11```
`Maximum average subarray starts from index 3`

### Complexity Analysis for Find K Length Subarray of Maximum Average

#### Time complexity

O(n*k) where n is the size of array and k is subarray size. Here we traverse k times for n-k numbers. So in the brought calculation, we say that the time complexity is O(n*k).

#### Space Complexity

O(1) because we just use some variables here.

## Approach 2

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

### Algorithm

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 the minimum value of an integer, such that no other is smaller than that. (Using INT_MIN)
b.    Update max_sum to sum of the first k elements, using the 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 the index to K.
b.    Here, we take the index and increment it until N and for every value of the index, we find the sum_here that is adding the present index element and subtracting the first element.

c.    We do this until the 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. Now, 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.

### Explanation for Find K Length Subarray of Maximum Average

arr[] = {`1, 12, -5, -6, 50, 3`}

Here the value of n is 6 and the int value of k is 2.

Start:
Sum_here = = 1 + 12 = 13
Therefore, here max_sum = 13.
We initialize index = 2, till index < 6 we compare sum_here with max_sum

For index = 2.
Sum_here = 13 – 1 + (-5) = 7
7 >13  -> False

For index = 3.
Sum_here = 7 – 12 + (-6) = -11
-11 >1  -> False
Therefore, max_sum = 2 and subarray position = 2.

For index = 4.
Sum_here = -11 – (-5) + 50 = 44
44 >13  -> True
Therefore, max_sum = 44 and subarray position = 3.

End.

Sum_here = 44 – (-6) + 3 = 53
53 >44  -> True
Therefore, max_sum = 53 and subarray position = 4.
Prints max_sum = 53 and subarray start position is = 4.
Therefore, the maximum subarray of size 2 starts from position 4.

### Implementation

#### C++ Program for Find K Length Subarray of Maximum Average

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int N,K;
cin>>N>>K;
int arr[N];
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
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;
}```

#### Java Program for Find K Length Subarray of Maximum Average

```import static java.lang.Integer.max;
import java.util.Scanner;

class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int N = sr.nextInt();
int K = sr.nextInt();
int arr[] = new int[N];
for(int i=0;i<N;i++)
{
arr[i] = sr.nextInt();
}
if(K>N)
{
System.out.println("No such subarray with that size possible");
}else{
int max_sum=-1; //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++;
}
System.out.println("Maximum average subarray starts from index " + pos_max);
}
}
}```
```6 2
1 12 -5 -6 50 3```
`Maximum average subarray starts from index 4`

### Complexity Analysis for Find K Length Subarray of Maximum Average

#### Time complexity

O(n) where n is the size of the array. Here we traverse the whole array and find the sum of the subarray of size k in constant time after 1st subarray.

#### Space complexity

O(1) because we use some variables to compute the final answer.

References

Translate »