Maximum average subarray of size k

Given an integer array and a number k, print the maximum sum subarray of size k.
Maximum average subarray of size k is a subarray (sequence of contiguous elements in the array) for which the average is maximum among all subarrays of size k in the array.
Average of k elements = (sum of k elements)/k
Since k > 0, the maximum sum subarray of size k will also be maximum average subarray of size k. So, the problem reduces to finding maximum sum subarray of size k in the array.

Please check out the video below for detailed explanation of the algorithm with animations.


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Algorithm/Insights

We use sliding window strategy for solving this.
Step 1: Find sum of first k elements in the input array. Initialize maxSum to the calculated sum and maxSumStartIndex = 0.
Step 2: Add next element to the sum and subtract first element from the sum. Check if this sum is greater than previous sum and update maxSum and maxSumStartIndex.
Step 3: Keep adding next element to the sum and removing first element from the sum to get sum of current sub array of size k and update maxSum and maxSumStartIndex whenever a greater sum is seen.
Step 4: Finally print k elements starting from maxSumStartIndex.


Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.saurabh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given an integer array and a number k, print the maximum sum subarray of size k.
 * 
 * @author Saurabh
 */
public class MaxAvgSubarray {

    private static int getMaxAvgSubarrayStartIndex(int input[], int k)
    {
        int n = input.length;
        if (k > n)
            throw new IllegalArgumentException("k should be less than or equal to n");
     
        if(k == n) {
            return 0;   // whole array is the solution
        }

        // Sum of first k elements
        int sum = input[0];
        for (int i = 1; i < k; i++)
            sum += input[i];
     
        // Initialized to first k elements sum
        int maxSum = sum;
        int maxSumIndex = 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
            sum = sum - input[i-k] + input[i] ;
            if (sum > maxSum)
            {
                maxSum = sum;
                maxSumIndex = i-k;
            }
        }
     
        // Return starting index of max avg sub array
        return maxSumIndex + 1;
    }
    
    public static void printMaxAvgSubarray(int[] input, int k) {
        System.out.print("Maximum average subarray of length " + k + " is:  ");
        int index = getMaxAvgSubarrayStartIndex(input, k);
        for(int i =0 ; i < k; i++) {
            System.out.print(input[index++] + " ");
        }
    }
    
    public static void main(String[] args) {
        int[] input = {11, -8, 16, -7, 24, -2, 3};
        int k = 3;
        printMaxAvgSubarray(input, k);
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer