Differences with Penalty
Here is an attempt at an $n^2$ DP-based algorithm:
Compute $M(\ell)$, the maximum such sum that uses only $a_1,\ldots,a_\ell$ (but it is not required that $a_\ell$ is used!). To compute $M(\ell)$ you have to take into account: (1) $M(\ell-1)$ and (2) all combinations of using $M(i-1)$, for some $i&lt;\ell$, and picking $a_i$ and $a_\ell$, on top of it. This looks like a linear outer loop with a linear inner loop. The penalty does not seem to hurt: just add $a_\ell-a_i-2$ in the latter case. A non-linear penalty would be a different story.