I recently encountered a problem and I am looking for an optimal approach, especially when $$$N$$$ and $$$Q$$$ are large.

The Problem:

Given an array $$$A$$$ of size $$$N$$$ ($$$A_1, A_2, \dots, A_N$$$). The array is circular, meaning $$$A_{N}$$$ is followed by $$$A_1$$$. We have $$$Q$$$ queries. Each query gives an integer $$$L$$$. For each query, we need to find the maximum sum of $$$L$$$ consecutive elements in this circular array.

• If $$$L \gt N$$$, the segment wraps around the array multiple times.

My Analysis:

Let $$$S$$$ be the sum of all elements in $$$A$$$. For a length $$$L$$$, we can decompose it into full cycles and a remainder:

Where $$$k = \lfloor L/N \rfloor$$$ and $$$r = L \pmod N$$$.

The maximum sum for length $$$L$$$ would be:

Where $$$\text{MaxSum}(r)$$$ is the maximum sum of a subarray of length $$$r$$$ in the circular array.

The Constraints & Issue:

• If $$$N, Q \le 5000$$$, I can precompute $$$\text{MaxSum}(k)$$$ for all $$$k \in [1, N]$$$ in $$$O(N^2)$$$ time using a sliding window on the doubled array, and answer queries in $$$O(1)$$$.

• However, if $$$N$$$ is up to $$$10^5$$$ and $$$Q$$$ is up to $$$10^5$$$, the $$$O(N^2)$$$ precomputation is too slow (TLE).

My Question:

Is there a known technique to compute $$$\text{MaxSum}(k)$$$ for all $$$k \in [1, N]$$$ faster than $$$O(N^2)$$$? Or is there another approach to handle these queries online without full precomputation in better than $$$O(N)$$$ per query?

Thank you!