# Maximum Average Subarray I
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-average-subarray-i)
Canonical: https://scaleengineer.com/dsa/problems/maximum-average-subarray-i
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array
---
## Problem
You are given an integer array `nums` consisting of `n` elements, and an integer `k`.

Find a contiguous subarray whose **length is equal to** `k` that has the maximum average value and return _this value_. Any answer with a calculation error less than `10-5` will be accepted.

**Example 1:**

**Input:** nums = [1,12,-5,-6,50,3], k = 4
**Output:** 12.75000
**Explanation:** Maximum average is (12 - 5 - 6 + 50) / 4 = 51 / 4 = 12.75

**Example 2:**

**Input:** nums = [5], k = 1
**Output:** 5.00000

**Constraints:**

* `n == nums.length`
* `1 <= k <= n <= 105`
* `-104 <= nums[i] <= 104`

# Approaches
## Brute Force Approach
This approach iterates through every possible contiguous subarray of length `k`, calculates the sum of each subarray, and finds the maximum sum. The maximum average is then this maximum sum divided by `k`.
**Time:** O(n * k). The outer loop runs `n-k+1` times, and for each iteration, the inner loop runs `k` times to calculate the sum. This results in a total of approximately `n * k` operations. · **Space:** O(1). We only use a few variables to store the sums and loop indices, regardless of the input size.
**Pros:** Simple to understand and implement.
**Cons:** Inefficient for large inputs, likely to result in a 'Time Limit Exceeded' error on competitive programming platforms due to the O(n*k) complexity.
### Explanation
The simplest way to solve this problem is to consider every possible subarray of length `k` one by one.

We can use a nested loop structure. The outer loop iterates through all possible starting indices of the subarray, from `0` to `n-k`.

For each starting index `i`, the inner loop calculates the sum of the elements from `nums[i]` to `nums[i+k-1]`.

We maintain a variable, say `maxSum`, to store the maximum sum found so far. After calculating the sum of a subarray, we compare it with `maxSum` and update `maxSum` if the current sum is greater.

After the loops complete, `maxSum` will hold the maximum sum of any contiguous subarray of length `k`. The final result is `maxSum / k`.

```java
public class Solution {
    public double findMaxAverage(int[] nums, int k) {
        long maxSum = Long.MIN_VALUE;
        int n = nums.length;
        for (int i = 0; i <= n - k; i++) {
            long currentSum = 0;
            for (int j = i; j < i + k; j++) {
                currentSum += nums[j];
            }
            maxSum = Math.max(maxSum, currentSum);
        }
        return (double) maxSum / k;
    }
}
```
### Algorithm
- Initialize a variable `maxSum` to a very small number (e.g., `Long.MIN_VALUE`).
- Iterate with an index `i` from `0` to `n-k`, where `n` is the length of the array. This index `i` will be the starting point of our subarray.
- For each `i`, create an inner loop with index `j` from `i` to `i+k-1` to calculate the sum of the current subarray.
- Store this sum in a variable `currentSum`.
- After the inner loop, compare `currentSum` with `maxSum` and update `maxSum = Math.max(maxSum, currentSum)`.
- After the outer loop finishes, return `maxSum / k`.

## Cumulative Sum (Prefix Sum) Approach
This approach involves pre-computing a cumulative sum array (also known as a prefix sum array). This allows for the calculation of the sum of any contiguous subarray in constant time. We then iterate through all possible subarrays of length `k`, calculate their sums using the pre-computed array, and find the maximum.
**Time:** O(n). It takes O(n) to build the prefix sum array and another O(n) to iterate through the subarrays to find the maximum sum. The total complexity is O(n) + O(n) = O(n). · **Space:** O(n). We need an additional array of size `n+1` to store the cumulative sums.
**Pros:** Efficient O(n) time complexity.; Conceptually separates the sum calculation from the search for the maximum.
**Cons:** Requires extra space proportional to the input size, which is less space-efficient than the sliding window approach.
### Explanation
The core idea is to create an auxiliary array, let's call it `prefixSum`, where `prefixSum[i]` stores the sum of all elements from the beginning of the original array up to index `i-1`.

The `prefixSum` array can be built in a single pass through the `nums` array: `prefixSum[i] = prefixSum[i-1] + nums[i-1]`.

Once we have this `prefixSum` array, the sum of any subarray from index `i` to `j` (inclusive) can be found in O(1) time using the formula `prefixSum[j+1] - prefixSum[i]`.

For our problem, we need the sum of subarrays of length `k`. A subarray starting at `i` ends at `i+k-1`. Its sum is `prefixSum[i+k] - prefixSum[i]`.

We can iterate from `i = 0` to `n-k`, calculate the sum for each subarray of length `k` using the prefix sum array, and keep track of the maximum sum.

The final result is the maximum sum found divided by `k`.

```java
public class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        long maxSum = Long.MIN_VALUE;
        for (int i = 0; i <= n - k; i++) {
            long currentSum = prefixSum[i + k] - prefixSum[i];
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return (double) maxSum / k;
    }
}
```
### Algorithm
- Create a `prefixSum` array of size `n+1` and initialize all its elements to 0.
- Iterate through the `nums` array from `i=0` to `n-1` and populate the `prefixSum` array: `prefixSum[i+1] = prefixSum[i] + nums[i]`.
- Initialize a variable `maxSum` to a very small number.
- Iterate from `i=0` to `n-k`.
- For each `i`, calculate the sum of the subarray `nums[i...i+k-1]` as `currentSum = prefixSum[i+k] - prefixSum[i]`.
- Update `maxSum = Math.max(maxSum, currentSum)`.
- After the loop, return `maxSum / k`.

## Sliding Window Approach
A more efficient approach is to use the sliding window technique. Instead of re-calculating the sum of each subarray from scratch, we can calculate the sum of the next subarray in constant time by subtracting the element that leaves the window and adding the element that enters the window.
**Time:** O(n). We calculate the sum of the first `k` elements in O(k) time. Then, we iterate through the rest of the array once, which takes O(n-k) time. The total time complexity is O(k + n - k) = O(n). · **Space:** O(1). We only use a constant amount of extra space for variables like `windowSum` and `maxSum`.
**Pros:** Highly efficient with linear time complexity.; Optimal solution for this problem in terms of both time and space.
**Cons:** Slightly more complex to reason about than the brute-force approach, but it's a standard and important technique.
### Explanation
This method avoids the redundant calculations of the brute-force approach. We start by computing the sum of the first `k` elements.

We initialize two variables: `windowSum` for the sum of the current window and `maxSum` to keep track of the maximum sum found so far. Both are initialized with the sum of the first `k` elements.

Then, we iterate through the array from the `k`-th element to the end. In each iteration, we 'slide' the window one step to the right.

This is done by adding the new element `nums[i]` to `windowSum` and subtracting the element that is no longer in the window, `nums[i-k]`.

After updating `windowSum`, we compare it with `maxSum` and update `maxSum` if `windowSum` is larger.

Finally, after iterating through the entire array, we return `maxSum / k`.

```java
public class Solution {
    public double findMaxAverage(int[] nums, int k) {
        long sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        
        long maxSum = sum;
        
        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - nums[i - k];
            maxSum = Math.max(maxSum, sum);
        }
        
        return (double) maxSum / k;
    }
}
```
### Algorithm
- Calculate the sum of the first `k` elements and store it in a variable `windowSum`.
- Initialize `maxSum` with the value of `windowSum`.
- Iterate from index `k` to `n-1` (where `n` is the length of the array).
- In each iteration `i`, update `windowSum` by adding the current element `nums[i]` and subtracting the element that just left the window, `nums[i-k]`. The formula is `windowSum = windowSum + nums[i] - nums[i-k]`.
- Update `maxSum = Math.max(maxSum, windowSum)`.
- After the loop, return `maxSum / k`.

# Solutions
### Java

```java
class Solution {
public
  double findMaxAverage(int[] nums, int k) {
    int s = 0;
    for (int i = 0; i < k; ++i) {
      s += nums[i];
    }
    int ans = s;
    for (int i = k; i < nums.length; ++i) {
      s += (nums[i] - nums[i - k]);
      ans = Math.max(ans, s);
    }
    return ans * 1.0 / k;
  }
}

```

### CPP

```cpp
class Solution {
public:
  double findMaxAverage(vector<int> &nums, int k) {
    int s = accumulate(nums.begin(), nums.begin() + k, 0);
    int ans = s;
    for (int i = k; i < nums.size(); ++i) {
      s += nums[i] - nums[i - k];
      ans = max(ans, s);
    }
    return static_cast<double>(ans) / k;
  }
};

```

### Python

```python
class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float: s = sum(nums[: k]) ans = s for i in range(k, len(nums)): s += nums[i] - nums[i - k] ans = max(ans, s) return ans / k

```