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.

How does Kadane's algorithm fail if you limit the size of the array you're keeping track of to k? — G. Bach
@G.Bach: Try doing it for the array in the question, when k=7. When you reach 5, the max array ending there is [8, -1, -1, 4, -2, -3, 5]. However, when you move to the 6, you need to drop the 8; that causes a chain reaction to drop the -1, -1, 4, -2, -3, because the largest subarray of length at most 7, ending at 6, is [5,6]. In other words, you need to keep track of which elements to "drop" as you walk the array, and a naive implementation leads to time proportional to n*k. — Steve D
You sure? You would have two pointers, one left one right, and each of them would traverse the array once, no? — G. Bach
@G.Bach: I would be very interested in seeing details on how that would work. I don't see how you can do it by modifying Kadane's algorithm, though: there are k subarrays that can stop at any given element (of lengths 1, 2, ..., k), and traversing them all takes n*k. — Steve D

Sorin Sorin · Accepted Answer · 2015-09-11T09:45:20

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

Maximal subarray with length constraint

1 Answers