# Maximum subarray sum of given length range

Can anyone please help me solve this better than $$O(|a-b| \cdot n)$$?

Given an array of both negative and positive numbers, we want to find the maximum sum of the elements in contiguous subarray having a length between $$a$$ and $$b$$.

Example

Input:

8 1 2

-1 13 -2 5 13 -5 2 2

Output: 18

Here a = 1 , b = 2

Although Maximum sum is 29, Max sum of length between [1-2] is 18

This answer explains an $$O(n)$$-time algorithm.

### Basic Ideas

The ideas are classic.

• "Sum of the elements in subarray" -- prefix sums.
• "Length between aand b" -- window of size b-a+1.
• "Maximum" -- maximum queue for the window

We will compute the array of prefix sums prefix_sums first. Then for each index s, we will compute the maximum elements of prefix_sums[s+a..s+b]. The difference between prefix_sum[s] and that maximum element is the maximum sum of a subarray that starts at index s + 1 and of length between a and b.

To compute the maximum element of prefix_sums[s+a..s+b], we will keep a dequeue of elements like (prefix_sums[i], i), decreasing in the pref_sums[i] part but increasing in the i part. When s is increased by 1, we will remove (prefix_sums[s+a-1], s+a-1) from the front of the dequeue if that element is in the dequeue, as well as append (prefix_sums[s+b], s+b) to the dequeue, popping out all previous elements with no greater prefix_sum-part from the back of the dequeue. Hence the maximum element of the queue will always be at its very front element.

### Implementation in Python

from collections import deque
from itertools import accumulate

# 1 <= a <= b <= n
n, a, b = map(int, input().split(" "))
prefix_sums = list(accumulate(map(int, input().split(" ")), initial=0))

d = b - a
# elements like (pre_sums[i], i),  decreasing in the
# pref_sums[i] part but increasing in the i part.
deq = deque()
for i in range(a, n + d + 1):
if deq and deq[0][1] < i - d:
deq.popleft()
if i <= n:
while deq and deq[-1][0] <= prefix_sums[i]:
deq.pop()
deq.append((prefix_sums[i], i))
if i >= b:
# deq[0][0] is the maximum elements of pre_sums[i-d..min(n, i)]



#### Complexity analysis

Prefix sums is computed in $$O(n)$$ time.
The outer for loop executes less than $$2n$$ iterations. Each prefix sum will be put into the dequeue once and popped out at most once.
Hence, the algorithm runs in $$O(n)$$ time. $$O(n)$$-space is used; however, it can be reduced to $$O(b-a+1)$$ easily if input and processing are done by streaming.

By augmenting an AVL tree you can implement a data structure that maintains a multi-set $$S$$ under the following $$O(\log |S|)$$-time operations:

• Add($$S, x$$): Add number $$x$$ to $$S$$.
• Offset($$S, x$$): Increase the value of all element in $$S$$ by number $$x$$.
• Delete($$S,x$$): Delete (one copy of) number $$x$$ from $$S$$
• Max($$S$$): Return the maximum element of $$S$$.

Let $$n$$ be the number of elements in the input array, and call $$a_i$$ the $$i$$-th element. Let $$\beta$$ be a parameter, and define $$\sigma_i$$ as the maximum sum of the elements of a subarray that ends with $$a_i$$ and has length between $$1$$ and $$\beta$$. You can compute all values $$\sigma_1, \dots, \sigma_n$$ in time $$O(n \log(1+\beta))$$ as follows:

• Initialize $$S=\emptyset$$, and $$\ell=0$$.
• For $$i=1, \dots,n$$:
• If $$i > \beta$$:
• Delete($$S$$, $$\ell$$)
• Decrement $$\ell$$ by $$a_{i-\beta}$$
• Offset($$S, a_i$$)
• Add($$S, a_i$$)
• Increment $$\ell$$ by $$a_i$$
• Set $$\sigma_i$$ to Max($$S$$)

At the end of the generic $$i$$-th iteration, the multi-set $$S$$ contains the sum of the elements of the contiguous (non-empty) subarrays ending with $$a_i$$ and having length at most $$\beta$$, while $$\ell$$ is the sum of the elements in the subarray ending with $$a_i$$ and having length $$\min\{\beta,i\}$$.

To solve your problem it suffices to compute all $$\sigma_i$$ for $$\beta=b-a+1$$ in time $$O(\log (b-a+1))$$ and return: $$\max_{i=a,\dots,n} \left\{ \sigma_{i-a+1} + \sum_{j=i-a+2}^{i} a_j \right\}.$$ Notice that, once the values $$\sigma_i$$ are known, this latter maximum can be evaluated in time $$O(n)$$ (since each sum can be found in constant time by updating the value of the previous sum). The overall time complexity is therefore $$O(n \log (b-a+1))$$.