1
$\begingroup$

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?

$\endgroup$
  • 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 S Jun 11 '17 at 9:48
  • $\begingroup$ That looks good. Can you write it up as an answer? $\endgroup$ – Lance Fortnow Jun 11 '17 at 13:47
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.