Maximal subarray with length constraint

Question

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.

Answer 1

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).