Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
1.1.
Problem Statement 
1.2.
Sample Examples 
2.
Brute Force Approach 
2.1.
Pseudocode
2.2.
Implementation in Python
2.3.
Implementation in Java
2.4.
Complexity Analysis 
3.
Optimized Approach 
3.1.
Pseudocode
3.2.
Implementation in Python
3.3.
Implementation in Java
3.4.
Complexity Analysis 
4.
Frequently Asked Questions 
4.1.
What is a subarray?
4.2.
What is the sliding window strategy?
4.3.
What are contiguous subarrays?
5.
Conclusion 
Last Updated: Mar 27, 2024
Easy

Find maximum average subarray of length k

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction 

In this blog, we will look at the approach to find the maximum average subarray possible if the numbers in the array are positive and negative. We will also discuss another approach for solving this problem other than a generalized approach.

Recommended topic about, kth largest element in an array and  Euclid GCD Algorithm

Problem Statement 

Given: An array of n integers with positive and negative values and the value of 'k' indicates the length of the output array.

Problem: Find the subarray with the maximum average of an array of the given size.

Sample Examples 

Input: 
7 3
ar[ ] = {8, -5, 16, -7, 24, -5, 6}

Output: 
Maximum subarray of size 3 starts at index 2.
Maximum subarray is: 16 -7 24

Explanation:   On traversing the array and comparing the sum of different subarrays, we get the sum of the maximum average subarray as 16 + (-7) + 24 = 33.

Brute Force Approach 

In the brute force approach, we will find the maximum average sum of the subarrays formed and store it in a temporary variable. Then, iteratively compare the maximum average sum of subarrays using two loops and update maximum value accordingly.

Pseudocode

  1. Check if the value of the subarray is possible or not. If k>n, no subarray is possible.
  2. Declare and initialize variables for use which are temp_sum = 0 and max_sum = INT_MIN.
  3. Find the individual sum of elements in all the possible subarrays of length k and compare the temp_sum with the max_sum at that point. If max_sum < temp_sum then update max_sum. 
  4. Run two loops, one from 0 to (n-k) and the second from 0 to (k-1). The second loop adds all the elements and finds the sum for each subarray of size k. If max_sum < temp_sum here, then we update max_sum and store the value of the position of starting index for the subarray.
  5. Print the starting index of the resulting subarray with the maximum average sum.

Implementation in Python

# Function to find the subarray of length 'k' with maximum average sum
def MaxAvgSum(ar, n, k):
    # Check here if a subarray of the given size of 'k' is possible or 
    # not, if k<n, then the subarray is not possible
    if (k > n):
        return -1
    if (k==n):
        return 0
 
    # Initialize variables for use
    temp_sum = 0
    max_sum = ar[0]
    index = 0
    # Run the loops for iteration
    for i in range(0, n-k):
        temp_sum = 0
        for j in range(0, k):
            temp_sum += ar[i+j]
        if(temp_sum > max_sum):
            max_sum = temp_sum
            index = i

    # Return starting index
    return index

    
# Main program
ar = [8, -5, 16, -7, 24, -5, 6]
k = 3
n = len(ar)
 
print("The maximum average subarray of length", k,"begins at index",
          MaxAvgSum(ar, n, k))

 

Implementation in Java

import java.util.Scanner;
class MaxAvgSum
{
    public static int main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int k = sr.nextInt();
        int ar[] = new int[n];
        for(int i=0;i<n;i++)
        {
            ar[i] = sr.nextInt();
        }
        if(k > n)
        {
          System.out.println("No such subarray possible");
          return -1;  
        }  
        int max_sum=-1; // For storing the maximum sum of such subarray 
        // with size K
        int temp_sum=0, index = 0; //maximum sum and starting position 
        // of subarray 
        for(int i=0; i<= (n-k); i++)
        {
            temp_sum=0;
          for(int j =0; j<k; j++)
            temp_sum += ar[i+j];
          if( temp_sum > max_sum)
          {
            max_sum = temp_sum;
            index = i;
          }
        }
        System.out.println("The maximum average subarray of length" + k + " starts from index " + index);
        return 0;
    }
}

 

Output:

Input: 7 3
Output: The maximum average subarray of length 3 begins at index 2.

 

Complexity Analysis 

Time Complexity: In this approach, the time complexity is O(n*k) as the implementation consists of nested loops. The first loop is from 0 to n , i.e. it traverses n times and the second loop runs from 0 to (n-k), i.e. it traverses k times. Therefore, the total time complexity is O(n*k).

Space Complexity: The space complexity of this approach is O(1) because the auxiliary space used is O(1).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach 

To find the maximum average sum out of the different subarrays formed by the array elements, we can run loops iteratively to find the sum of initial k elements of the array and 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. Now compare the updated sum values and compare the maximum sum of each subarray.

Pseudocode

  1. Check whether a subarray of the given size of ‘k’ is possible or not. If k>n, no subarray is possible.
  2. Initialize variables for storing the temporary value of sum in temp_sum and maximum value of sum in max_sum. Now, in the input array find the sum of initial k elements. Initialize max_sum with the value of the calculated sum and declare a variable max_sum_start_index = 0.
  3. Add the next consecutive element to the sum and subtract the first element from the sum. Then, check if this sum is greater than the previously calculated sum and update the value of max_sum and max_sum_start_index. 
  4. Add the following elements to the sum iteratively and keep on removing the first element from the sum to obtain the sum of the current subarray of size k and update max_sum and max_sum_start_index whenever the sum is greater than the previous sum.
  5. Print the values of k elements starting from max_sum_start_index.

Explanation with an example:

Implementation in Python

# Function to find the subarray of length 'k' with maximum average sum
def MaxAvgSum(ar, n, k):
    # Check here if a subarray of the given size of 'k' is possible or 
    # not, if k<n, then the subarray is not possible
    if (k > n):
        return -1
    if (k==n):
        return 0
 
    # Initialize variables for use
    temp_sum = ar[0]
    # Run the first loop from 1 to k to get the sum of subarray
    # to get temp_sum for comparison
    for i in range(1, k):
        temp_sum += ar[i]

    # Initialize sum of first k elements
    max_sum = temp_sum
    max_sum_start_index = 0
 
    # Calculate sum of remaining subarrays
    for i in range(k,n):
        temp_sum = temp_sum-ar[i-k]+ar[i];
        if(temp_sum > max_sum):
             max_sum =  temp_sum
             max_sum_start_index = i-k+1

    # Return starting index
    return max_sum_start_index

    
# Main program
ar = [8, -5, 16, -7, 24, -5, 6]
k = 3
n = len(ar)
 
print("The maximum average subarray of length", k,"begins at index",
          MaxAvgSum(ar, n, k))

 

Implementation in Java

public class MaxAvgSum {
 
    private static int getMaxAvgSubarrayStartIndex(int ar[], int k)
    {
        int n = ar.length;
        if (k > n)
            throw new IllegalArgumentException("k should be less than or equal to n");
      
        if(k == n) {
            return 0;   // complete array is the solution
        }
 
        // Calculate sum of first k elements
        int temp_sum = ar[0];
        for (int i = 1; i < k; i++)
            temp_sum += ar[i];
      
        // Initialize first k elements sum
        int max_sum = temp_sum;
        int max_sum_start_index = 0;
      
        // Sum of remaining sub arrays
        for (int i = k; i < n; i++)
        {
            // Remove first element of the current window and add next element to the window
            temp_sum = temp_sum - ar[i-k] + ar[i] ;
            if (temp_sum > max_sum)
            {
                max_sum = temp_sum;
                max_sum_start_index = i-k;
            }
        }
      
        // Return starting index of maximum average subarray
        return max_sum_start_index + 1;
    }
    
    public static void printMaxAvgSumSubarray(int[] ar, int k) {
        int index = getMaxAvgSubarrayStartIndex(ar, k);
        System.out.print("The maximum average subarray of length " + k + " begins at index " + index);
    }
    
    public static void main(String[] args) {
        int[] ar = {8, -5, 16, -7, 24, -5, 6};
        int k = 3;
        printMaxAvgSumSubarray(ar, k);
    }
}

 

Output: 

The maximum average subarray of length 3 begins at index 2.

Complexity Analysis 

Time Complexity: In this approach, we have used the loop from 1 to k and k to n to traverse over the given array, which means that we are iterating over every element of the array n times; therefore, the program's complexity will be O(n). During this implementation, the counter variable i is incremented or decremented by a constant value accordingly, so we assign the complexity of O(n).

Space Complexity: The auxiliary space used for this program is O(1) so the space complexity is O(1).

Check out this problem - Subarray With 0 Sum

Frequently Asked Questions 

What is a subarray?

Subarray is a part of a section of the array which is referred to according to the given condition.

What is the sliding window strategy?

The strategy involves creating a window, or a subset of an array, and moving it up or down depending on the condition.

What are contiguous subarrays?

Contiguous subarrays have continuous indexes in the array.

Conclusion 

This article discussed the approach to finding the maximum average subarray of a given length k. We have also implemented the pseudocode for the program in Python and Java and have understood the working of the algorithm with the help of an example.

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Find the sum of all the distinct elements in an array
Next article
Tandem
Live masterclass