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 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://www.youtube.com/watch?v=VT4bZV24QNo&ab_channel=Pepcoding (This was is in Hindi)