Input: An array of n positive and negative numbers and a number k.
输入:n个正数和负数的数组和数字k。
Output: Subarray of at least k consecutive elements with maximum sum of elements divided by number of elements in the subarray.
输出:至少k个连续元素的子数组，元素的最大和除以子数组中元素的数量。
O(n^2) algorithm is easy. Does anyone have a better algorithm for this?
O(n ^ 2)算法是很容易的。有人有更好的算法吗?
1 个解决方案
#1
2
You can use binary search.
可以使用二进制搜索。
For a searched value x, consider the array b[i] = a[i] - x. Now find the maximum sum subarray of length at least k.
对于搜索值x，考虑数组b[i] = a[i] - x，现在找到长度至少为k的最大和子数组。
This works because the average of a subarray of length k is (a[p] + ... + a[p + k - 1]) / k. So we have:
这是因为长度为k的子数组的平均值是(a[p] +……+ a[p + k - 1]) / k。
(a[p] + ... + a[p + k - 1]) / k >= avg
a[p] + ... + a[p + k - 1] >= avg * k
(a[p] - avg) + ... + (a[p + k - 1] - avg) >= 0
So, if you binary search for the average, by substracting it from each element, if you can find a positive-sum subarray (find the maximum one and check if it's positive) of length at least k, then avg is a valid answer: continue to search in [avg, max_avg] to see if you can find a better one. If not, reduce search to [0, avg].
如果你二进制搜索的平均,对照组从每个元素,如果你能找到一个正和子数组(找到最大的一个,检查如果是积极的)的长度至少k,然后avg是一个有效的回答:继续搜索(avg,max_avg),看看你可以找到一个更好的。如果不是，则将搜索减少到[0,avg]。
#1
2
You can use binary search.
可以使用二进制搜索。
For a searched value x, consider the array b[i] = a[i] - x. Now find the maximum sum subarray of length at least k.
对于搜索值x，考虑数组b[i] = a[i] - x，现在找到长度至少为k的最大和子数组。
This works because the average of a subarray of length k is (a[p] + ... + a[p + k - 1]) / k. So we have:
这是因为长度为k的子数组的平均值是(a[p] +……+ a[p + k - 1]) / k。
(a[p] + ... + a[p + k - 1]) / k >= avg
a[p] + ... + a[p + k - 1] >= avg * k
(a[p] - avg) + ... + (a[p + k - 1] - avg) >= 0
So, if you binary search for the average, by substracting it from each element, if you can find a positive-sum subarray (find the maximum one and check if it's positive) of length at least k, then avg is a valid answer: continue to search in [avg, max_avg] to see if you can find a better one. If not, reduce search to [0, avg].
如果你二进制搜索的平均,对照组从每个元素,如果你能找到一个正和子数组(找到最大的一个,检查如果是积极的)的长度至少k,然后avg是一个有效的回答:继续搜索(avg,max_avg),看看你可以找到一个更好的。如果不是，则将搜索减少到[0,avg]。