我必须解决一个类似于最大子数组问题的问题。我必须找到平均值大于 k 的最大子数组。我想到了以下技巧。我可以将大小为 n 的数组 A[] 转换为 B[]，其中 B[i] = A[i] - k。所以现在平均值必须> 0。但是平均值大于零并不仅仅意味着总和大于零吗？所以我可以直接应用 Kadane 的算法。我对吗？（总是在有 1 个正值的约束下）
问问题
1351 次
2 回答
4
不，kadane 的算法仍然会为您找到总和最大的子数组......我必须解决同样的问题。到目前为止，我发现如果我们如上所述创建数组 B，然后创建包含数组 B 的部分和的数组 C，那么我们正在寻找的最大间隔 (i,j) 具有相同的数字对于 i 和 j ！！！例如：
数组 A 是：1 10 -1 -1 4 -1 7 2 8 1 ......给定的 k 是 5，那么数组 B 是：-4 5 -6 -6 -1 -6 2 -3 3 -4数组 C 是：-4 1 -5 -11 -12 -18 -16 -19 -16 -20 所以我们要查找的子数组是 [7,2,8]，长度为 3，并且第一个和最后一个元素是-16！！！！
编辑：我忘了告诉我们正在搜索 O(n) 或 O(n*logn) 算法.... @lets_solve_it 你是对的，但你的算法是 O(n^2) 这对于我们要处理的数据。我很接近用 C++ 中的函数映射来解决它，它就像一个哈希表。我认为这是正确的方向，因为这里数组 C 的元素与其索引有直接关系！我们的教授还告诉我们，另一种可能的解决方案是再次制作数组 C 然后采用（特殊？）支点进行快速排序....但我不完全理解我们期望快速排序做什么。
于 2012-11-20T09:42:31.350 回答
2
@panos7：
创建数组 C（部分求和数组）后，您将寻找 C、Ci 和 Cj 的两个值，
这样，Cj>=Ci，并且 (ji) 尽可能“大”。(ji) --> 最大。
然后返回 ji。
在你的例子中， -16>=-18 所以你返回 ji=9-6=3
这是正确的答案！
于 2012-11-22T22:05:51.070 回答