algorithm - 平均大于或等于 k ​​的最长连续子数组

Question

考虑一个包含 N 个整数的数组。找到最长的连续子数组，使其元素的平均值大于（或等于）给定数 k。

显而易见的答案具有 O(n^2) 复杂度。我们能做得更好吗？

Answer 1

我们可以通过在 O(n) 时间内从所有值中减去 k 来将此问题简化为总和 >= 0 的最长连续子数组。现在让我们计算前缀和：

index    0     1     2     3     4     5     6
array          2     -3    3     2     0     -1
prefix   0     2     -1    2     5     5     4

现在这个问题是找到距离最远的两个索引prefix_right - prefix_left >= 0。让我们创建一个新的前缀索引数组并按前缀排序，然后是索引。

index    2     0     1     3     6     4     5
prefix   -1    0     2     2     4     5     5

然后我们可以做一个从右到左的扫描，为每个前缀计算前缀大于或等于当前前缀的最大索引：

index    2     0     1     3     6     4     5
prefix   -1    0     2     2     4     5     5
maxind   6     6     6     6     6     5     5

现在，让我们回到原来的前缀数组。对于每个前缀-索引对，我们对新数组进行二进制搜索以找到最小前缀 >= 当前前缀。我们从二进制搜索前缀的 maxind 中减去当前前缀的索引，以检索从当前索引开始的最佳可能序列长度。取最大长度的序列。

由于排序和 n 次二进制搜索，该算法为 O(n log n)。

Answer 2

我们可以在 O(n) 时间和 O(n) 空间复杂度内解决问题：
我尝试过简单且最优的方法。
简而言之，这个问题涉及两个步骤：
(1) 从每个 ar[i] 中减去 k，并在新数组中找到累积值。让我们将新数组称为 cumArr[]。
(2) 现在问题变成在 CumArr[] 中找到 max(j-1) 使得 j>i 并且 cumArr[j]>cumArr[i]。这一步是一个著名的问题，可以在很多地方找到。

这是运行代码的详细信息：http: //codeshare.io/Y1Xc8

可能有可以轻松处理的小角落案例。
让我知道你的想法的朋友。