Non adjacent sum: Why do we need to include or exclude the current element?

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:

• https://structy.net/problems/non-adjacent-sum

• https://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/

• https://www.techiedelight.com/maximum-sum-of-subsequence-with-no-adjacent-elements/

• https://www.youtube.com/watch?v=6w60Zi1NtL8

• https://www.youtube.com/watch?v=VT4bZV24QNo&ab_channel=Pepcoding (This was is in Hindi)

• https://www.codingninjas.com/codestudio/problem-details/maximum-sum-of-non-adjacent-elements_843261

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

• $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:

-
either you have not taken $T[i+1]$, that is, $j_p

-
either you have taken $T[i+1]$, that is $j_p = i+1$. In this case, $j_{p-1}

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


StackExchange Computer Science Q#150277, answer score: 3