输入：一个由 n 个正负数和一个数 k 组成的数组。
输出：至少有 k 个连续元素的子数组，其中元素的最大总和除以子数组中的元素数。
O(n^2) 算法很简单。有没有人对此有更好的算法？
问问题
2865 次
1 回答
3
您可以使用二进制搜索。
对于搜索值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].
于 2012-10-26T21:14:54.960 回答