Maximum subarray of bounded length

Question

I'm giving an array $A[0..n-1]$ and an integer $w$. The goal is to find indices $i,j$ that maximize

$$\Phi(i,j) = A[i] + A[i+1] + \dots + A[j-1],$$

subject to the requirements that 0ドル \le i \le j \le n$ and $j \le i+w$. Or, in other words, I want to find the sequential window of width at most $w$ such that the sum of the numbers in the window is maximized.

Is there an $O(n)$ time algorithm for this task? Or, what is the most efficient algorithm for this task?

There is a trivial $O(nw)$ time algorithm, but I can't see how to do better than that. If $w=\infty$, Kadane's algorithm solves this in $O(n)$ time, but I can't see how to generalize it to my problem. So, can we do better than $O(nw)$ time?

I encountered this problem in the context of an image processing task I'm facing.

• Yuval Filmus: With a heap you might be able to do this in $O(n\log w)$.

Answer 1

The problem you are describing can be solved in $O(n)$.

Let's define the prefix sum as: $$\text{psum}[i] = \sum_{0 \le j \le i} A[j]$$ Then your function can be expressed as: $$\Phi(i, j) = \text{psum}[j-1] - \text{psum}[i-1]$$

Assuming we fix the right boundary $j-1$ (we want to find the window of size at most $w$ ending at $j-1$ with the maximal sum). It should be easy to see, that this window has the sum: $$\text{psum}[j-1] - \min_{i \ge j - w}\left\{\text{psum}[i-1]\right\}$$

For the actuall implementation we use a data structure called Minimum Queue. It is a queue (FIFO) that does the normal push/pop operations in amortized constant time and it additionally supports extracting the minimum of its current stored elements in constant time.

With it we can find the maximal window in linear time:

best = 0
initialize min_queue
min_queue.push(psum[-1]) # psum[-1] can be defined as 0
for j = 1 to n:
 if len(min_queue) > w:
 min_queue.pop()
 cur = psum[j-1] - min_queue.min()
 best = max(best, cur)
 min_queue.push(psum[j-1]) 

One way of implementing a Minimum Queue is to store the elements in a dequeue using value-index pairs. And you keep this queue in non-decreasing order, i.e. you only store the subset of pairs that are or can become the minimum at some point and ignore the remaining elements. This means whenever you push a new element, you remove all previous elements that are bigger from the back of the queue, since the currently added element will dominate them at all times. Therefore the minimum will always be the first element.

This approach, and also two (similar) alternatives are described on cp-algorithms.com.