Maximize $\sum_{i\equiv r \pmod{m}} a_i$ over $m,r$ Given a circle with $n$ equal segments. On each segment there is an
integer. We want select segments at equal distance, maximizing the sum of integers on selected segments.

I have an algorithm with runtime $O(n^2)$ as follows:
First calculate maximum sum of segments at distance one. Second calculate maximum sum of segments at distance two, and so on. Return maximum of all above values.
According to the teacher, there is a solution with runtime $O(n\log n)$, but I cannot find it.
Denote the numbers by $a_0,\ldots,a_{n-1}$. We want to maximize, over all $m \mid n$ and $0 \leq r &lt; m$, the sum of all $a_i$ such that $i \equiv r \pmod{m}$.
Let $p_1,\ldots,p_k$ be the prime divisors of $n$. Either $m = n$, or $m \mid (n/p_i)$. In the latter case, we can fold $a$ into an array $b^{(n/p_i)}$ of size $n/p_i$, and solve the problem there, recursively. If we use dynamic programming, then each $b^{(m)}$ will explored once, for each $m \mid n$.
What is the running time of this algorithm? The work done at $b^{(m)}$ takes time $O(m\rho(m))$, where $\rho(m) = O(\log m / \log\log m)$ is the number of distinct prime factors of $m$ (the upper bound on $\rho(m)$ follows from $n \geq \rho(m)!$). It follows that the total running time is proportional to
$$
\sum_{m \mid n} m\rho(m) \leq \frac{\log n}{\log\log n} \sum_{m \mid n} m = \frac{\log n}{\log\log n} \sigma(n) = O(n\log n),
$$
since the divisor sum function satisfies $\sigma(n) = O(n\log\log n)$.