输入:n个正负数和一个数字k的数组。
输出:至少包含 k 个连续元素的子数组，其中元素的最大总和除以子数组中的元素数量。
O(n^2) 算法很简单。有没有人有更好的算法？
最佳答案
您可以使用二分搜索。
对于搜索值 x ，考虑数组 b[i] = a[i] - x 。现在找到长度至少为 k 的最大和子数组.
这是有效的，因为长度为 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
所以，如果你对平均值进行二分搜索，通过从每个元素中减去它，你是否可以找到一个长度至少为 k 的正和子数组(找到最大的一个并检查它是否为正)。 ，然后avg是有效答案:继续在 [avg, max_avg] 中搜索看看是否能找到更好的。如果没有，请将搜索减少到 [0, avg] .
关于algorithm - 查找具有最大元素总和/数量的子数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13093602/