Find maximum average subarray of length k

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))

You can also try this code with Online Python Compiler

Run Code

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

You can also try this code with Online Java Compiler

Run Code

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 -

• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Max circular subarray sum
• Subarray sums divisible by k

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System 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 problems, interview 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!