具有长度约束的最大子数组

Question

我在 CS.SE 上问过这个问题，但没有得到回应。

我最近面临以下面试问题：

给定一个数组 A 和一个整数 k，找到一个具有最大和的连续子数组，加上约束，这个子数组的长度最多为 k。

所以，如果A=[8, -1, -1, 4, -2, -3, 5, 6, -3]我们得到以下不同值的答案k：

+---+------------------------------+
| k |           subarray           |
+---+------------------------------+
| 1 | [8]                          |
| 7 | [5,6]                        |
| 8 | [8, -1, -1, 4, -2, -3, 5, 6] |
+---+------------------------------+

如果n是数组的长度A，那么使用修改后的优先级队列，我能够及时回答这个问题O(n lgk)；有没有办法改善这一点O(n)？请注意，O(n)当 k=n 时，Kadane 算法会及时运行。

Answer 1

你可以在 O(n) 中完成。就是这样。

• 让我们定义B部分和的数组B[x] = sum(i in (0, x+1), a[i])
• 现在问题变成了找到索引 q 和 w 使得w<=q, q-w <=k, 和B[q] - B[w]是可能的最大值。

为此，我们将遍历数组 B 以找到 q。由于B[q]是固定的，我们B[w]在最小值时最大化表达式。我们保持一个双端队列来快速找到 w。双端队列将保持潜在最小值的位置。要更新它：取出第一个元素，因为它在您想要的 k 间隔之外，从后面提取所有大于当前位置值的值，最后在后面插入当前位置。

应该是这样的

for (q in len(b))
  // The minimum is too far behind
  if !deque.empty() && q - deque.front() > k: deque.pop_front() 
  // Remove the less optimal positions from the queue.
  while (!deque.empty() && b[deque.back()] > b[q]) deque.pop_back() 
  deque.push_back(q)

  if (b[q] - b[deque.front()] > best_so_far) UpdateBestSoFar();

由于内部的原因，它可能看起来像 O(N^2) 但事实并非如此。每个元素都被插入到双端队列中，并且只提取一次。所以while迭代的总数是O(N)。