Assume that we are given a vector of integers of length $N$ such that the largest element in the vector is $K$ (where $K$ is quite small). Given this vector $a$ we are also given a vector of weights $w$ that has the elements $2N-2i+1$, for $i=1, ..., N$.
The goal is to proceed step by step picking an integer from either side of the vector $a$, and then removing the picked number, so that we maximize a sum where first term that we pick is multiplied by $w_1$, second by $w_2$ etc. So in total we do $N$ steps after which the vector $a$ is fully ’consumed’.
Is there a sufficiently fast algorithm that finds the maximum? In other words, an algorithm that solves this faster than trying out all the $2^N$ possible combinations of taking from left and right.
Let $a\in \mathbb{Z}^N$ be the initial vector you care about. For any $1\leq i\leq j\leq N$, write $a_{i:j}$ for the vector of length $j-i+1$ obtained by keeping the elements in $a$ indexed in $\{i,\ldots,j\}$. For any vector $b$ (of arbitrary length), define $\textbf{val}(b)$ for the optimal value in your problem, so that you care about $\textbf{val}(a)$.
The key observation is that if some vector $b$ has length $M$, then
\begin{equation} \textbf{val}(b) = \max\{(2M-1)\cdot b_1 +\textbf{val}(b_{2:M}),(2M-1)\cdot b_M +\textbf{val}(b_{1:M-1})\}. \end{equation} This is seen by considering the value of picking the first element or the last element to multiply by $2M-1$, and then getting the optimal value on the remaining vector.
A simple algorithm to compute $\textbf{val}(a)$ proceeds by computing $\textbf{val}(a_{i:j})$ for all $1\leq i\leq j\leq N$. You can do this for all $i\leq j$ such that $j-i=k$ for $k=0,\ldots,N-1$ iteratively just knowing it for all $i'\leq j'$ such that $j'-i'=k-1$ using the inductive equation. The base case of $k=0$ (i.e. $i=j$) is easy as for all $i\leq N$,
\begin{equation} \textbf{val}(a_{i:i}) = 1\cdot a_i. \end{equation}
You can then use the recursive equation to determine $\textbf{val}(a_{i:j})$ for all $i$ and $j=i+1$, and then so on when $j-i=2$, etc. The value you care about is $\textbf{val}(a)=\textbf{val}(a_{1:N})$. There are $O(N^2)$ such subproblems in total and computing the value of each subproblem can be done in $O(1)$ operations using the recursive equation if done in the correct order.