# LeetCode 643: Maximum Average Subarray I

## Problem Restatement

We are given an integer array `nums` and an integer `k`.

We need to find a contiguous subarray whose length is exactly `k` and has the maximum average value.

Return that maximum average.

The answer is accepted if its error is less than `10^-5`. The subarray must be contiguous and must have length exactly `k`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer array `nums` and integer `k` |
| Output | Maximum average of a contiguous subarray of length `k` |
| Constraint | The subarray length must be exactly `k` |

Example function shape:

```python
def findMaxAverage(nums: list[int], k: int) -> float:
    ...
```

## Examples

Example 1:

```python
nums = [1, 12, -5, -6, 50, 3]
k = 4
```

The possible windows of length `4` are:

| Window | Sum | Average |
|---|---:|---:|
| `[1, 12, -5, -6]` | `2` | `0.5` |
| `[12, -5, -6, 50]` | `51` | `12.75` |
| `[-5, -6, 50, 3]` | `42` | `10.5` |

The maximum average is:

```python
12.75
```

Example 2:

```python
nums = [5]
k = 1
```

The only subarray is `[5]`.

So the answer is:

```python
5.0
```

## First Thought: Compute Every Window Sum From Scratch

A direct approach is to try every subarray of length `k`.

For each starting index, compute the sum of the next `k` numbers.

```python
class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        best_sum = float("-inf")

        for start in range(len(nums) - k + 1):
            current_sum = 0

            for i in range(start, start + k):
                current_sum += nums[i]

            best_sum = max(best_sum, current_sum)

        return best_sum / k
```

This is correct, but it repeats too much work.

Adjacent windows share most of their elements.

For example:

```text
[1, 12, -5, -6]
[12, -5, -6, 50]
```

The second window removes `1` and adds `50`.

We do not need to recompute the whole sum.

## Key Insight

Since every valid subarray has the same length `k`, maximizing the average is the same as maximizing the sum.

So we only need to find the maximum sum of any window of length `k`.

When the window slides one step to the right:

```text
old window: nums[i-k], ..., nums[i-1]
new window: nums[i-k+1], ..., nums[i]
```

The new sum is:

```python
new_sum = old_sum - nums[i - k] + nums[i]
```

This gives an `O(n)` solution.

## Algorithm

1. Compute the sum of the first `k` elements.
2. Store it as both `current_sum` and `best_sum`.
3. Iterate from index `k` to the end of the array.
4. For each new index:
   1. Add `nums[i]`.
   2. Remove `nums[i - k]`.
   3. Update `best_sum`.
5. Return `best_sum / k`.

## Implementation

```python
class Solution:
    def findMaxAverage(self, nums: list[int], k: int) -> float:
        current_sum = sum(nums[:k])
        best_sum = current_sum

        for i in range(k, len(nums)):
            current_sum += nums[i]
            current_sum -= nums[i - k]

            best_sum = max(best_sum, current_sum)

        return best_sum / k
```

## Code Explanation

We start by computing the first full window:

```python
current_sum = sum(nums[:k])
best_sum = current_sum
```

Then each loop step slides the window by one position:

```python
current_sum += nums[i]
current_sum -= nums[i - k]
```

The value `nums[i]` enters the window.

The value `nums[i - k]` leaves the window.

After updating the window sum, we update the best sum:

```python
best_sum = max(best_sum, current_sum)
```

Finally:

```python
return best_sum / k
```

returns the maximum average.

## Correctness

The first window sum is computed exactly for `nums[0:k]`.

For every later index `i`, the algorithm transforms the previous window sum into the next window sum by adding the new rightmost element and removing the old leftmost element. Therefore, `current_sum` is always the sum of the current contiguous subarray of length `k`.

The algorithm compares every such window sum with `best_sum`, so after all windows are processed, `best_sum` is the maximum sum among all contiguous subarrays of length `k`.

Because all valid subarrays have the same length `k`, the subarray with maximum sum also has maximum average. Therefore, `best_sum / k` is the correct answer.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Each element enters and leaves the window at most once |
| Space | `O(1)` | Only a few variables are stored |

## Testing

```python
def run_tests():
    s = Solution()

    assert abs(s.findMaxAverage([1, 12, -5, -6, 50, 3], 4) - 12.75) < 1e-5
    assert abs(s.findMaxAverage([5], 1) - 5.0) < 1e-5
    assert abs(s.findMaxAverage([-1], 1) - (-1.0)) < 1e-5
    assert abs(s.findMaxAverage([0, 4, 0, 3, 2], 1) - 4.0) < 1e-5
    assert abs(s.findMaxAverage([-5, -2, -3, -4], 2) - (-2.5)) < 1e-5
    assert abs(s.findMaxAverage([10, 10, 10], 3) - 10.0) < 1e-5

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Official sample | Checks normal sliding window behavior |
| Single element | Minimum input |
| Negative single element | Handles negative averages |
| `k = 1` | Best average is the maximum element |
| All negative values | Must choose the least negative average |
| `k = n` | Only one window exists |