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?
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ 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. $\endgroup$– Thomas SCommented Jun 11, 2017 at 9:48
-
$\begingroup$ That looks good. Can you write it up as an answer? $\endgroup$– Lance FortnowCommented Jun 11, 2017 at 13:47
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
