Optimization problem: Maximize the sum of minimum. 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.
 A: 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:


*

*Here is a program
written in Ruby,
for those who want to experiment a bit more with this problem.
Sample output
here or
here or
here.
It generates random $N$-vectors and also checks if the optimized equations 
$(\#)$ give the same results like the original $(*)$.

*Observation: The changes of the sums 
$$
   \frac{\Delta}{\Delta c} \sum\limits_{i = a(c)}^{b(c)}t(i, c)
   $$ 
seem to behave similar to the derivatives of the parameter integrals 
$$
   \frac{\partial}{\partial c} \int\limits_{a(c)}^{b(c)} t(x, c) \, dx =
   t(b(c),c) \, b'(c) - t(a(c), c) \, a'(c) + 
   \int\limits_{a(c)}^{b(c)} \!\! \frac{\partial}{\partial c} t(x, c) \, dx
   $$   

A: 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.
