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, Commented Sep 11, 2015 at 7:15
@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
– Steve D, Commented Sep 11, 2015 at 7:57
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, Commented Sep 11, 2015 at 8:21
@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
– Steve D, Commented Sep 11, 2015 at 9:08

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

14

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

answered Sep 11, 2015 at 9:45

Sorin

12k25 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

j_random_hacker Over a year ago

I believe this is correct, but it would help to mention that you maintain the invariant that positions listed in the deque correspond to nondecreasing values of B[] -- this is what allows you to be confident that deque.front() is always a minimum-producing position, instead of having to search through every element in the deque looking for the smallest.

Steve D Over a year ago

This is great! It is very similar to how I did it too: I essentially was fixing w and searching for an optimal q. To do that I kept a heap maintained so I could quickly get the max B[q]. this answer not only is correct, but improves my original solution.

Jason Hu Over a year ago

are you sure? how can you hold the invariance of increasing B? take op's example, you will have B == [0, 8, 7, 6,10 ...]. this just doesn't sound correct.

Jason Hu Over a year ago

oh yeah. i got it. god, it's so smart.

Jacob Steinebronn Over a year ago

For those looking to learn more about this deque technique, it's called a Min/Max queue, and finds its most basic use cases in problems like these.

Devd · Accepted Answer · 2022-10-25 05:42:59Z

@Sorin idea implemented in Java.

class HelloWorld {
public static void main(String[] args) {
    int[] arr = {8, -1, -1, 4, -2, -3, 5, 6, -3};
    int k = 8;
    
    int[] prefixSum = new int[arr.length+1];
    for(int i=0; i<arr.length; i++){
        prefixSum[i+1] = prefixSum[i] + arr[i];
    }
    
    Deque<Integer> dq = new ArrayDeque<>();
    int maxSum = 0;
    for(int i=0; i<prefixSum.length; i++){
        if(!dq.isEmpty() && i-dq.peekFirst() > k){
            dq.pollFirst();
        }
        
        while(!dq.isEmpty() && prefixSum[dq.peekLast()] > prefixSum[i]){
            dq.pollLast();
        }
        
        dq.addLast(i);
        
        if(prefixSum[i] - prefixSum[dq.peekFirst()] > maxSum){
            maxSum = prefixSum[i] - prefixSum[dq.peekFirst()];
        }
    }
    
    System.out.println(maxSum);
  }}

Collectives™ on Stack Overflow

Maximal subarray with length constraint

2 Answers 2

5 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related