Maximum subarray sum of given length range

Question

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

Prob : https://cses.fi/problemset/task/1644

Answer 1

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()
answer = -1 << 63
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)]
 answer = max(answer, deq[0][0] - prefix_sums[i - b])
print(answer)

Complexity analysis

Prefix sums is computed in $O(n)$ time.
The outer for loop executes less than 2ドルn$ 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.

Answer 2

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