具有长度约束的最大子数组 [英] Maximal subarray with length constraint

问题描述

我在CS.SE上提出了此要求，但没有得到答复.

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

给定一个数组A和一个整数k，找到一个带有a的连续子数组 最大和，加上约束，此子数组的长度最多为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)?请注意，当k = n时，Kadane的算法会在O(n)时间运行.

解决方案

您可以在O(n)中进行操作.就是这样.

• 让我们定义部分和B[x] = sum(i in (0, x+1), a[i])
的数组B
• 现在问题变成了查找索引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).

I asked this over at CS.SE, but got no response.

I was recently faced with the following interview question:

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.

So, if A=[8, -1, -1, 4, -2, -3, 5, 6, -3] then we get the following answers for different values of k:

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

If n is the length of the array A, then using a modified priority queue, I was able to answer this question in time O(n lgk); is there a way to improve this to O(n)? Note that Kadane's algorithm runs in O(n) time when k=n.

解决方案

You can do it in O(n). Here's how.

• Let's defined array B of partial sums B[x] = sum(i in (0, x+1), a[i])
• Now the problem becomes find index q and w such that w<=q, q-w <=k, and B[q] - B[w] is the maximum value possible.

To do that we will go through the array B to find q. Since B[q] is fixed we maxmize the expression when B[w] is the minimum value. We keep a double ended queue to quickly find w. The deque will keep the positions of the potential minimums. To update it you: take out the first element because it is outside of the k interval you wanted, extract all the values from the back that are larger the the value at the current position and finally insert the current position in the back.

Should be something like this

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();

It may look like O(N^2) because of the inside while but it's not. Each element is inserted once into the deque and extracted exactly once. So the total number of while iterations is O(N).

这篇关于具有长度约束的最大子数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！