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

Question

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

我最近遇到了以下面试问题:

Given an array A, and an integer k, find a contiguous subarray with a maximal sum, with the added constraint this subarray has length at most 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。双端队列将保留潜在最小值的位置。要更新它:取出第一个元素，因为它在您想要的 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 但它不是。每个元素都被插入到双端队列中一次，并且恰好被提取一次。所以 while 迭代的总数是 O(N)。