Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Given positive integers $L$ and a set of non-negative integers $N$.
Find maximum of: $$\large \sum_{i = 1}^{4L}\ N_i\cdot(\min(\vert i - c\vert, 4L - \vert i - c\vert))$$
with $c \in \{1, 2,\dots ,4L\}$ and $\frac {\text {number of } N_i > 0} {L}$ is small (about $\frac 1 {100}$)
How can I solve this and similar problems efficiently? Thanks.
Problem: I assume the problem is $$ \begin{align} S &= \max_{c \in \{1, \ldots, 4L\}} \sum_{i=1}^{4L} N_i \min \left(|i-c|, 4L-|i-c|\right) \\ &= \max_{c \in \{1, \ldots, 4L\}} T(c) \end{align} \quad (*) $$
Complexity Simple Search: A simple search of $(*)$ over all $c$-values would require about $(4L)^2$ term evaluations, needing 1 $+$, 1 $\cdot$, 2 $-$, 1 $\min(.,.)$ and 1 $|.|$ calculation each.
Lemma 1: The change $\Delta T$ for increasing $c$ is:
$$ \Delta T(c) := T(c+1) - T(c) $$
It can be calculated recursively:
$$ \begin{align} \Delta T(1) &:= N_1 - \sum_{i=2}^{2L+1} N_i + \sum_{i=2L+2}^{4L} N_i \\ \Delta T(c) &:= \Delta T(c-1) + 2(N_{c} - N_{2L + c}) \quad c \in \{ 2, \ldots, 2L \} \end{align} \quad (**) $$
Lemma 2: The change has a symmetry: $$ \Delta T(c) = -\Delta T(c - 2L), \quad c \in \{ 2L+1, \ldots, 4L \} $$
Thus we can calculate the $2L$ values of $\Delta T$ in the second half of the $c$-interval faster, because we can make use of the values from the first half.
Quick Summation: Calculate the relative sum vector $Q$: $$ \begin{align} Q(1) &:= 0 \\ Q(c) &:= Q(c-1) + \Delta T(c-1) \\ \end{align} \quad c \in \{ 2, \cdots, 4L \} $$
Lemma 3: The $c^*$ which maximizes $Q(c)$ will maximize $T(c)$ as well.
Solution: Determine $c^*$ according to lemma 3 and the quick summation procedure. Then calculate
$$ S = T(c^*) $$
using the original defintion $(*)$ or even better using the optimized term evaluation:
$$ \begin{align} T_{L->R}(c) &:= \sum_{i = 1}^{c-1} N_i \, (c-i) + \sum_{i = c+1}^{2L+c-1} N_i \, (i-c) + \sum_{i = 2L+c}^{4L} N_i \, (4L - (i-c)) \\ & \quad c \in \{ 1, \ldots, 2L \} \\ T_{R->L}(c) &:= \sum_{i = 1}^{c - 2L} N_i \, (4L - (c-i)) + \sum_{i = c - 2L + 1}^{c-1} N_i \, (c-i) + \sum_{i = c + 1}^{4L} N_i \, (i-c) \\ & \quad c \in \{ 2L+1, \ldots, 4L \} \end{align} \quad (\#) $$
The optimized term $(\#)$ avoids minimum and absolute value operations. Its greater benefit is that it allows to determine the differences for lemma 1.
Complexity of the Solution: The complexity relative to the simple search has been reduced to less than $16 L$ $+$, $12 L$ $-$ and $6L$ $\cdot$ operations. Or roughly from quadratic to linear. In both cases not considering the similar $4L$ comparisons for the extremum search.
Bonus Lemma 1: The same procedure works for searching the minimum sum efficiently, just replace $\max$ with $\min$.
Bonus Lemma 2: The $N_i$ can be arbitrary real numbers.
Derivation of the Optimized Terms: We can avoid the minimum calculations in $(*)$ by using $T_{L\to R}$ for the $c$-values from $1$ up to $c_s = 2L$ and then using $T_{R\to L}$. We further split those sums after $i_{s, L\to R} = 2L+c-1$ and $i_{s, R\to L} = c - 2L$:
$$ \begin{align} T_{L->R}(c) &= \sum_{i = 1}^{2L+c-1} N_i \, |i-c| + \sum_{i = 2L+c}^{4L} N_i \, (4L - (i-c)) \\ T_{R->L}(c) &= \sum_{i = 1}^{c - 2L} N_i \, (4L - (c-i)) + \sum_{i = c - 2L + 1}^{4L} N_i \, |i-c| \end{align} $$
And we can split up two sums further to avoid the decisions during absolute value calculations, getting $(i-c)$ and $(c-i)$ factors. This yields $(\#)$.
Proof Lemma 1: The change $\Delta T$ for increasing $c$ is: $$ \Delta T(c) := T(c+1) - T(c) = \sum_{i=1}^c N_i - \sum_{i=c+1}^{2L+c} N_i + \sum_{i=2L+c+1}^{4L} N_i, \quad c \in \{ 1, \ldots, 2L \} \quad (\#\#) $$ This has been derived from $(\#)$ by analyzing how that expression changes from $c$ to $c+1$. It is a discrete analogon to differentiation. The expression is simpler than $(*)$ but still contains the information to determine the optimum.
Applying this idea again: If one knows $\Delta T(c)$, one can calculate $\Delta T(c+1)$ using:
$$ \Delta^2 T(c) := \Delta T(c+1) - \Delta T(c) = 2(N_{c+1} - N_{2L+c+1}) $$
This has been derived from $(\#\#)$. The result is the recursive scheme $(**)$.
Proof Lemma 2: Start with the second branch from $(\#)$. Determine the difference like in the proof of lemma 1. Compare the result with $(\#\#)$.
Proof Lemma 3: The relative sum $Q$ differs only by a constant from $T$ $$ Q(c) = T(c) - T(1). $$
Appendix:
If $c$ is an integer, it is worth noting that full search is maybe the fastest way to solve your problem. Trying out all possible values $c=1,\dots,4L$ is not critical in your case as the problem is one-dimensional.
