Dynamic programming, coming up with an algorithm I've been banging my head against the wall for the past two days and can't seem to come up with anything useful. The problem that needs to be solved is the following: I get an array of integers and I must return an array containing the elements that would give the maximum sum with the following condition: If I select an element, then I cannot use the one before or after it. I think I must, like it often is with dynamic programming, somehow order my results in a matrix, but I have no idea how to go about it. Any help is greatly appreciated.
For each $m$, let $\sigma(m)$ be the maximum sum of non-adjacent values among the first $m$ values of the array $A$. Then:
$$
\begin{align*}
&amp;\sigma(0) = 0, \\
&amp;\sigma(1) = A(1), \\
&amp;\sigma(m) = \max(A(m) + \sigma(m-2), \sigma(m-1))
\end{align*}
$$
As an exercise, now try to solve similar problems in which you slightly modify the constraints. For example, suppose that if you select an element then you are not allowed to use $a$ elements before or after it; or that among any $b$ adjacent elements, you are allowed to choose at most $c$.