最大子阵列变化

Question

我必须解决一个问题，就像最大子数组问题一样。我必须找到平均值大于k的最大子数组。我想到了下面的技巧。我可以将大小为n的数组A[]转换为B[]，其中Bi = Ai - k，所以现在平均值必须大于0。但是平均值大于零不意味着和大于零吗？所以我可以直接应用Kadane的算法。我说的对吗？(总是在有1个正值的约束下)

Answer 1

不，kadane的算法仍然会为你找到和最大的子数组…我必须解决同样的问题。到目前为止，我已经发现，如果我们像你上面提到的那样创建数组B，然后创建包含数组B的部分和的数组C，那么我们正在查找的最大间隔(i，j)对于i和j具有相同的数字！例如：

数组A是:1 10 -1 -1 4 -1 7 2 8 1 .....and给定的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，然后进行(特殊的？)轴心来做quicksort....but我不完全理解我们期望快速排序做什么。

Answer 2

@panos7：

创建数组C (部分和数组)后，您将查找C、Ci和Cj这两个值，

使得，Cj>=Ci，和，(j-i)尽可能地“大”。(j-i) -->最大

然后返回j-i。

在您的示例中，-16>=-18，因此您返回j-i=9-6=3

这才是正确的答案！