# 644    Maximum Average Subarray II

## 644. [Maximum Average Subarray II](https://leetcode.com/problems/maximum-average-subarray-ii/description/)

## 1. Question

Given an array consisting of`n`integers, find the contiguous subarray whose **length is greater than or equal to**`k`that has the maximum average value. And you need to output the maximum average value.

**Example 1:**

```
Input: [1,12,-5,-6,50,3], k = 4

Output: 12.75

Explanation:

when length is 5, maximum average value is 10.8,
when length is 6, maximum average value is 9.16667.
Thus return 12.75.
```

**Note:**

1. 1 <=`k`<=`n`<= 10,000.
2. Elements of the given array will be in range \[-10,000, 10,000].
3. The answer with the calculation error less than 10^-5 will be accepted.

## 2. Implementation

**(1) Brute Force**

```java
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        double res = Integer.MIN_VALUE;

        for (int i = 0; i <= n - k; i++) {
            double sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];

                if (j - i + 1 >= k) {
                    res = Math.max(res, sum * 1.0 / (j - i + 1));
                }
            }
        }
        return res;
    }
}
```

**(2) Binary Search**

```java
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double start = Integer.MAX_VALUE;
        double end = Integer.MIN_VALUE;

        for (int num : nums) {
            start = Math.min(start, num);
            end = Math.max(end, num);
        }

        int n = nums.length;

        while (end - start > 1e-5) {
            double mid = start + (end - start) / 2;

            if (isValidSubarray(nums, mid, k)) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        return start;
    }

    public boolean isValidSubarray(int[] nums, double target, int k) {
        int n = nums.length;
        double minSum = 0, sum = 0, prevSum = 0;

        for (int i = 0; i < k; i++) {
            sum += nums[i] - target;
        }

        if (sum >= 0) {
            return true;
        }

        for (int i = k; i < n; i++) {
            sum += nums[i] - target;
            prevSum += nums[i - k] - target;
            minSum = Math.min(minSum, prevSum);

            if (sum > minSum) {
                return true;
            }
        }
        return false;
    }
}
```

## 3. Time & Space Complexity

**Brute Force**: 时间复杂度O(n^2)， 空间复杂度O(1)

**Binary Search:** 时间复杂度O(n \* log(max - min)), 空间复杂度O(1)