Skip to content

644. Maximum Average Subarray II πŸ”’

Description

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is greater than or 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:
- When the length is 4, averages are [0.5, 12.75, 10.5] and the maximum average is 12.75
- When the length is 5, averages are [10.4, 10.8] and the maximum average is 10.8
- When the length is 6, averages are [9.16667] and the maximum average is 9.16667
The maximum average is when we choose a subarray of length 4 (i.e., the sub array [12, -5, -6, 50]) which has the max average 12.75, so we return 12.75
Note that we do not consider the subarrays of length < 4.

Example 2:

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

 

Constraints:

  • n == nums.length
  • 1 <= k <= n <= 104
  • -104 <= nums[i] <= 104

Solutions

We note that if the average value of a subarray with length greater than or equal to $k$ is $v$, then the maximum average number must be greater than or equal to $v$, otherwise the maximum average number must be less than $v$. Therefore, we can use binary search to find the maximum average number.

What are the left and right boundaries of binary search? The left boundary $l$ must be the minimum value in the array, and the right boundary $r$ is the maximum value in the array. Next, we binary search the midpoint $mid$, and judge whether there exists a subarray with length greater than or equal to $k$ whose average value is greater than or equal to $mid$. If it exists, then we update the left boundary $l$ to $mid$, otherwise we update the right boundary $r$ to $mid$. When the difference between the left and right boundaries is less than a very small non-negative number, i.e., $r - l < \epsilon$, we can get the maximum average number, where $\epsilon$ represents a very small positive number, which can be $10^{-5}$.

The key to the problem is how to judge whether the average value of a subarray with length greater than or equal to $k$ is greater than or equal to $v$.

We assume that in the array $nums$, there is a subarray with length $j$, the elements are $a_1, a_2, \cdots, a_j$, and its average value is greater than or equal to $v$, i.e.,

$$ \frac{a_1 + a_2 + \cdots + a_j}{j} \geq v $$

Then,

$$ a_1 + a_2 + \cdots + a_j \geq v \times j $$

That is,

$$ (a_1 - v) + (a_2 - v) + \cdots + (a_j - v) \geq 0 $$

We can find that if we subtract $v$ from each element in the array $nums$, the original problem is transformed into a problem of whether the sum of the elements of a subarray with length greater than or equal to $k$ is greater than or equal to $0$. We can use a sliding window to solve this problem.

First, we calculate the sum $s$ of the differences between the first $k$ elements and $v$. If $s \geq 0$, it means that there exists a subarray with length greater than or equal to $k$ whose element sum is greater than or equal to $0$.

Otherwise, we continue to traverse the element $nums[j]$. Suppose the current sum of the differences between the first $j$ elements and $v$ is $s_j$. Then we can maintain the minimum value $mi$ of the sum of the differences between the prefix sum and $v$ in the range $[0,..j-k]$. If $s_j \geq mi$ exists, it means that there exists a subarray with length greater than or equal to $k$ whose element sum is greater than or equal to $0$, and we return $true$.

Otherwise, we continue to traverse the element $nums[j]$ until the entire array is traversed.

The time complexity is $O(n \times \log M)$, where $n$ and $M$ are the length of the array $nums$ and the difference between the maximum and minimum values in the array, respectively. The space complexity is $O(1)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        def check(v: float) -> bool:
            s = sum(nums[:k]) - k * v
            if s >= 0:
                return True
            t = mi = 0
            for i in range(k, len(nums)):
                s += nums[i] - v
                t += nums[i - k] - v
                mi = min(mi, t)
                if s >= mi:
                    return True
            return False

        eps = 1e-5
        l, r = min(nums), max(nums)
        while r - l >= eps:
            mid = (l + r) / 2
            if check(mid):
                l = mid
            else:
                r = mid
        return l

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double eps = 1e-5;
        double l = 1e10, r = -1e10;
        for (int x : nums) {
            l = Math.min(l, x);
            r = Math.max(r, x);
        }
        while (r - l >= eps) {
            double mid = (l + r) / 2;
            if (check(nums, k, mid)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return l;
    }

    private boolean check(int[] nums, int k, double v) {
        double s = 0;
        for (int i = 0; i < k; ++i) {
            s += nums[i] - v;
        }
        if (s >= 0) {
            return true;
        }
        double t = 0;
        double mi = 0;
        for (int i = k; i < nums.length; ++i) {
            s += nums[i] - v;
            t += nums[i - k] - v;
            mi = Math.min(mi, t);
            if (s >= mi) {
                return true;
            }
        }
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double eps = 1e-5;
        double l = *min_element(nums.begin(), nums.end());
        double r = *max_element(nums.begin(), nums.end());
        auto check = [&](double v) {
            double s = 0;
            for (int i = 0; i < k; ++i) {
                s += nums[i] - v;
            }
            if (s >= 0) {
                return true;
            }
            double t = 0;
            double mi = 0;
            for (int i = k; i < nums.size(); ++i) {
                s += nums[i] - v;
                t += nums[i - k] - v;
                mi = min(mi, t);
                if (s >= mi) {
                    return true;
                }
            }
            return false;
        };
        while (r - l >= eps) {
            double mid = (l + r) / 2;
            if (check(mid)) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return l;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func findMaxAverage(nums []int, k int) float64 {
    eps := 1e-5
    l := float64(slices.Min(nums))
    r := float64(slices.Max(nums))
    check := func(v float64) bool {
        s := 0.0
        for _, x := range nums[:k] {
            s += float64(x) - v
        }
        if s >= 0 {
            return true
        }
        t := 0.0
        mi := 0.0
        for i := k; i < len(nums); i++ {
            s += float64(nums[i]) - v
            t += float64(nums[i-k]) - v
            mi = math.Min(mi, t)
            if s >= mi {
                return true
            }
        }
        return false
    }
    for r-l >= eps {
        mid := (l + r) / 2
        if check(mid) {
            l = mid
        } else {
            r = mid
        }
    }
    return l
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function findMaxAverage(nums: number[], k: number): number {
    const eps = 1e-5;
    let l = Math.min(...nums);
    let r = Math.max(...nums);
    const check = (v: number): boolean => {
        let s = nums.slice(0, k).reduce((a, b) => a + b) - v * k;
        if (s >= 0) {
            return true;
        }
        let t = 0;
        let mi = 0;
        for (let i = k; i < nums.length; ++i) {
            s += nums[i] - v;
            t += nums[i - k] - v;
            mi = Math.min(mi, t);
            if (s >= mi) {
                return true;
            }
        }
        return false;
    };
    while (r - l >= eps) {
        const mid = (l + r) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    return l;
}

Comments