lintcode617. Maximum Average Subarray II
Intuition
Find maximum average subarray which length should be greater or equal to given length k
.
the minimum average is the minimum of array, the maximum average is the maximum of array.
binary search
mid
between minimum and maximum, ifsum(subarray) - mid * len(subarray) > 0
, thenminimum = mid
how to judge it in binary search?
use pre-sum array
sum[]
denotessum(nums[0] - mid, ..., nums[i] - mid)
mn
denotes the minimum sum from0
toi - k
if
i >= k && sum[i] > mn
, prove that there issum(nums[j] - mid, ..., num[i] - mid) > 0
, the real average will greater thanmid
.
Solution
Last updated