4
$\begingroup$

The problem goes like this:

Write a function, nonAdjacentSum, that takes in an array of numbers as an argument. The function should return the maximum sum of non-adjacent elements in the array. There is no limit on how many elements can be taken into the sum as long as they are not adjacent.

I am struggling to understand the solutions that are online regarding this dynamic programming problem.

All types of solutions one way or other, start by stating that when looping through each element of an array you can either include the current item or exclude the current item. And my question is Why is that? There seems a really basic thing I am missing here.

What I understand clearly is that, When I am looping through the array, if I am observing the element at position i then I cannot take element at i-1 and i+1 but any elements beyond them are possible.

Now in order to solve this via Dynamic programming, I need to reduce the problem size and solve the base case. I think this is where exclusion is coming from, but I don't understand why though.

Some solutions I have read/viewed are:

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

To really understand dynamic programming algorithm, it is usually convenient to explain (in natural language) what the subproblems your algorithm is solving dynamically.

Let $T$ be the table of length $n$ that is given in the input.

Subproblems: for every $i \leq n$, we compute the maximum sum $S_i$ of non-adjacent elements in the array $T[1..i]$ (the array containing only the first $i$ elements of $T$).

In the end, we want to output $S_n$, so if we solve these subproblems for every $i\leq n$, we are done.

Now you need to explain how you solve base cases and how you propagate dynamically.

Base cases: for $i=1$, it is easy since $T[1..1]$ only contains one element. Thus $S_1 = \max(0, T[1])$ (it may be that $T[1]$ is negative, and you do not want to take it).

Dynamic step: assume you have computed $S_1, \dots, S_i$, how do you compute $S_{i+1}$ from there?

What we usually do is that we take an optimal solution for the subproblem we want to solve at this step and see how it can be computed from optimal solutions for already solved subproblems.

Here, consider an optimal solution of the problem for the array $T[1..i+1]$. That is, take $j_1, \dots, j_p \in [1;i+1]$ such that:

  • $1 \leq j_1 < \dots < j_p \leq i+1$
  • $j_{k+1} - j_k > 1$ (no adjacent elements)
  • $\sum_{k=1}^p T[j_k] = S_{i+1}$ that is, $j_1,\dots,j_p$ are optimal for the task we want to solve on $T[1..i+1]$.

How does $j_1, \dots, j_p$ relate with optimal solutions of other subproblems? There are two cases:

  1. either you have not taken $T[i+1]$, that is, $j_p < i+1$. In this case, $j_1, \dots, j_p \in [1;i]$. Now I claim that $S_{i+1} = S_i$. Indeed, if $\sum_{k=1}^p T[j_k] \neq S_i$, then we could have found other non adjacent positions with a greater sum (by definition of $S_i$), contradicting the way we chose $j_1,\dots,j_p$.

  2. either you have taken $T[i+1]$, that is $j_p = i+1$. In this case, $j_{p-1} < i$ (no adjacent elements are taken). In other words, $j_1,\dots, j_{p-1} \in [1;i-1]$. Again, I claim that $\sum_{k=1}^{p-1} T[j_k] = S_{i-1}$, otherwise, you could have picked non-adjacent positions with a greater sum, contradicting the definition of $j_1, \dots, j_p$. Hence $S_{i+1} = T[i+1]+S_i$.

Since at least one of the previous case happens, we have: $S_{i+1} = \max(S_i, S_{i-1}+T[i+1])$.

Now you have it: you only have to compute $S_i$ for every $i$ following this scheme. You can do it in an array of size $n$. But you can do better: you only need to remember $S_{i-1}$ and $S_i$ to compute $S_{i+1}$. Thus, you can solve the problem by only maintaining two variables $a, b$. At the end of step $i$, you will enforce the condition that $a = S_{i-1}$ and $b = S_{i}$.

a = 0 # convention : S_0 is 0
b = max(T[1], 0) # b is S_1

for i in rang(2, n+1):
  # At this point, a=S_{i-2} and b=S_{i-1}
  tmp = b # save S_{i-1} before erasing it
  b = max(b, a+T[i]) # S_i is max(S_{i-1}, S_{i-2}+T[i])
  a = tmp # a is now S_{i-1} and b is S_i


return b
Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thank you for taking time to answer this. I am stuck at these points and see how it relates with optimal solution for already solved subproblems. and Here: take non-adjacent elements of T[1..i+1] maximizing the sum (ie, optimal for Si+1). Can you please expand on these? $\endgroup$
    – Starx
    Apr 2, 2022 at 10:31
  • $\begingroup$ Edited by explicitly taking an optimal solution. $\endgroup$
    – holf
    Apr 2, 2022 at 12:19
  • $\begingroup$ Thanks. My lack of knowledge made me more confused tbh. In your recent update what does j represent and how does it differ from S? $\endgroup$
    – Starx
    Apr 3, 2022 at 10:50
  • $\begingroup$ $j$ are the indices of an optimal solution. $S$ is the value of the optimal solution. $\endgroup$
    – holf
    Apr 3, 2022 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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