Maximum Average Sub-array of K length

February 2, 2021

maximum average subarray

Maximum Average Sub-array of K length in Java:

Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.

Input: [1,12,-5,-6,50,3]

k = 4

Output:

The maximum average subarray of length 4 begins at index 1

Explanation:

Maximum average is (12-5-6+50)/4 = 51/4 = 12.75

Algorithm:

  • START
  • Use function MaxAverage 
int MaxAverage(int arr[], int size, int k) 
    { 
        
        // Check if ‘k’ is valid 
        if (k > size) 
            return -1; 
    
        // Compute sum of first ‘k’ elements 
        int sum = arr[0]; 
        for (int i = 1; i < k; i++) 
            sum += arr[i]; 
    
        int maximumsum = sum, maxend = k-1; 
    
        // Compute sum of remaining subarrays 
        for (int i = k; i < size; i++) 
        { 
            sum = sum + arr[i] – arr[i-k]; 
            if (sum > maximumsum) 
            { 
                maximumsum = sum; 
                maxend = i; 
            } 
        } 
    
        
        return maxend – k + 1; 
    } 
  • END

Java code:

// Java program to find maximum average subarray 
// of given length. 

import java.io.*; 

class prepinsta { 

    static int MaxAverage(int arr[], int size, int k) 
    { 
        
        // Check if ‘k’ is valid 
        if (k > size) 
            return –1; 
    
        // Compute sum of first ‘k’ elements 
        int sum = arr[0]; 
        for (int i = 1; i < k; i++) 
            sum += arr[i]; 
    
        int maximumsum = sum, maxend = k-1; 
    
        // Compute sum of remaining subarrays 
        for (int i = k; i < size; i++) 
        { 
            sum = sum + arr[i] – arr[i-k]; 
            if (sum > maximumsum) 
            { 
                maximumsum = sum; 
                maxend = i; 
            } 
        } 
    
        
        return maxend – k + 1; 
    } 

    public static void main (String[] args) 
    { 
        int arr[] = {1, 12, –5, –6, 50, 3}; 
        int k = 4; 
        int size = arr.length; 
        System.out.println( “The maximum average”
                    + ” subarray of length “ + k 
                    + ” begins at index “
                    + MaxAverage(arr, size, k)); 
    } 
} 



Output:

The maximum average subarray of length 4 begins at index 1