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!
