有长度限制的最大子数组。

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)? 请注意，Kadane的算法运行在? O(n) 当k=n的时候。

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，deque会保留潜在最小值的位置。要更新它，你需要：取出第一个元素，因为它在你想要的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();

因为里面有while，所以看起来像O(N^2)，但其实不然。每个元素在deque中插入一次，提取一次。所以，while迭代的总次数是O(N)。