<p>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.</p>

CC BY-SA 3.0
2017-06-11T14:32:56.193Z
2017-06-11T14:32:56.193Z
Thomas S
<p>Given a sequence $a_1,\ldots,a_n$, find a $k$ and numbers $1\leq i_1&lt; \dots&lt; i_{2k}\leq n$ that maximizes $(\sum_{j=1}^{k}(a_{i_{2j}}-a_{i_{2j-1}}))-2k$. I can get an $n^3$ algorithm using dynamic programming. Is there a better algorithm?</p>

CC BY-SA 3.0
2017-06-11T09:48:42.520Z
Probably there is an oversight in the following attempt at an n2 DP algorithm: Compute M(ℓ), the maximum such sum that uses only a1,\ldots,aℓ (but it is not required that aℓ is used!). To compute M(ℓ) you have to take into account: (1) M(ℓ−1) and (2) all combinations of using M(i−1), for some i<ℓ, and picking ai and aℓ, 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.
Thomas S
CC BY-SA 3.0
2017-06-11T13:47:20.157Z
That looks good. Can you write it up as an answer?
Lance Fortnow
<ds.algorithms>
Differences with Penalty
Lance Fortnow
# Differences with Penalty

(Asked by: username_0 on 2017-06-10)

Given a sequence $a\_1,\ldots,a\_n$, find a $k$ and numbers $1\leq i\_1< \dots< i\_{2k}\leq n$ that maximizes $(\sum\_{j=1}^{k}(a\_{i\_{2j}}-a\_{i\_{2j-1}}))-2k$. I can get an $n^3$ algorithm using dynamic programming. Is there a better algorithm?

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: Probably there is an oversight in the following attempt at an n2 DP algorithm: Compute M(ℓ), the maximum such sum that uses only a1,\ldots,aℓ (but it is not required that aℓ is used!). To compute M(ℓ) you have to take into account: (1) M(ℓ−1) and (2) all combinations of using M(i−1), for some i<ℓ, and picking ai and aℓ, 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.  
> **username_0**: That looks good. Can you write it up as an answer?  

---

## 1 answers

### Answer by username_1 on 2017-06-11. Score: 1 | Accepted answer

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<\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.


---

