# How to calculate the maximum sum over all arrays?

Following question was asked in a online hackathon that has been concluded. Given arrays $A_1,\ldots,A_n$ of length $\ell_1,\ldots,\ell_n$, we want to find cyclically rotate each array in a way which maximizes $$\sum_{i=1}^{n-1} i|A_i[\ell_i] - A_{i+1}[1]|.$$

For example, on input $2,3,1 \mid 3,2 \mid 4,5$ the best cyclic rotation is $2,3,1 \mid 3,2 \mid 5,4$, and so the answer is $1|1-3| + 2|2-5| = 8$.

There could be up to $10^5$ arrays, and the sum of all elements in all arrays can be at most $10^6$.

I tried solving this by focusing on the two last arrays, but this turned out to be the wrong approach. I am unable to figure out the correct one. How can this be calculated efficiently?

• Any assumption on the size of each array? – md5 Oct 13 '17 at 11:49
• @md5 sum of all elements over all arrays will be less than 10^6. – Tom Oct 13 '17 at 12:07

You can solve this using dynamic programming. For each $1 \leq m \leq n$ and $1 \leq t_m \leq \ell_i$, calculate the maximal value of $\sum_{i=1}^{m-1} i|A_i[\ell_i]-A_{i+1}[1]|$ given that $A_m$ is rotated by $t_m$ places. This solution takes time $O(\sum_{i=1}^{n-1} \ell_i \ell_{i+1}) = O(\ell^2/n)$, where $\ell = \sum_{i=1}^n \ell_i$.
We can significantly improve on this algorithm by noticing that the objective function depends on the $i$th array via $\pm (i-1) A_i[1] \pm i A_i[\ell_i]$. This means that the shift we choose must maximize one of the following four quantities: \begin{align*} +(i-1)A_i[1] + iA_i[\ell_i], \;+(i-1)A_i[1] - iA_i[\ell_i], \\-(i-1)A_i[1] + iA_i[\ell_i], \;-(i-1)A_i[1] - iA_i[\ell_i]. \end{align*} This means that there are at most four values of $t_m$ that we need to consider (and at most two for $m \in \{1,n\}$). We can find these value in $O(\sum_{i=1}^{n-1} \ell_i) = O(\ell)$, and the dynamic programming part now takes only $O(n)$. In total, we obtain an $O(\ell)$ algorithm, that is, a linear time algorithm, which is asymptotically optimal.
• You use dynamic programming: for each $1 \leq m \leq n$ and for each of the up to four relevant values of $t_m$, you calculate the maximal value of $\sum_{i=1}^{m-1} i|A_i[\ell_i]-A_{i+1}[1]|$ given that $A_m$ is rotated by $t_m$ places. – Yuval Filmus Oct 13 '17 at 13:56