Maximize $\sum_{i\equiv r \pmod{m}} a_i$ over $m,r$
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)$.