The problem here is pretty similar to other binary search problems we had like #369 and #368. We pick some target value, try to find if there is some subarray whose length ≥ k that at least has the target value as average. If it does, we can look for higher values. Else, we need to look for lower values.
While looking if there is such a subarray, we look for differences between averages. If s_i is equal to sum of all elemenets up to some index i, a subarray with average v up to that would have the sum i·v. s_i-i·v - s_j-j·v ≥ 0 would prove that there is a subarray of length i-j that has an average ≥ v. Since the first term also includes the second term in its total, we have to subtract it to get the difference from the average subarray. Finding some j, i-j ≥ k would imply that such a subarray exists.
Resolves: #240
Algorithm:
The problem here is pretty similar to other binary search problems we had like #369 and #368. We pick some target value, try to find if there is some subarray whose length ≥ k that at least has the target value as average. If it does, we can look for higher values. Else, we need to look for lower values.
While looking if there is such a subarray, we look for differences between averages. If
s_iis equal to sum of all elemenets up to some indexi, a subarray with averagevup to that would have the sumi·v.s_i-i·v - s_j-j·v ≥ 0would prove that there is a subarray of lengthi-jthat has an average ≥v. Since the first term also includes the second term in its total, we have to subtract it to get the difference from the average subarray. Finding somej, i-j ≥ kwould imply that such a subarray exists.