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

- Check if the value of the subarray is possible or not. If k>n, no subarray is possible.
- Declare and initialize variables for use which are temp_sum = 0 and max_sum = INT_MIN.
- 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.
- 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.
- 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).