1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jun 8 '17 at 15:04
  • $\begingroup$ We get asked a lot about how to approach dynamic programming problems, so we've written some general reference material on the subject: cs.stackexchange.com/tags/dynamic-programming/info. Please study the material there, try applying the methods described there, and then if you're still stuck, I suggest you edit the question to show what progress you've made so far in applying that systematic approach and at which step you got stuck. $\endgroup$ – D.W. Jun 8 '17 at 18:19
1
$\begingroup$

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*} &\sigma(0) = 0, \\ &\sigma(1) = A(1), \\ &\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$.

$\endgroup$
  • $\begingroup$ Thank you, I created a recursive solution from these definitions and then a bottom-up DP solution that seems to work. $\endgroup$ – Max Jun 8 '17 at 20:47

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.