Find K Length Subarray of Maximum Average

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;
}

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

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;
}

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