











Maximum Average Sub-array of K length


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
Login/Signup to comment