To address with DP, work through the array, keeping track of the max at each position until you get to the last value of the array. You should start with the base cases defined before iterating through the remainder of the array.

max @ position 0: value @ 0

max @ position 1: either:

• value @ 0
• value @ 1

from that point forward, the max of the next position is either:

1. the current value at that position
2. the max value found so far
3. the max value from 2 positions back plus the current value

keep track of the max at each position until you get to the last position of the array

Java solution:

  public static int maxSubsetSum(int[] arr) {
    if (arr.length == 0) return 0;
    arr[0] = Math.max(0, arr[0]);
    if (arr.length == 1) return arr[0];
    arr[1] = Math.max(arr[0], arr[1]);
    for (int i = 2; i < arr.length; i++)
      arr[i] = Math.max(arr[i-1], arr[i]+arr[i-2]);
    return arr[arr.length-1];
  }

This assumes that the empty set is a valid subset for this problem. It also assumes we're not going to need the input array for anything else, as it butchers that.

Edit: checks for length of 0 & 1 (not checked by problem). Thanks @umanggupta

I think this problem could use a better definition of what a subset is. Can a single element be a subset? The examples seem to say that it can't, because all of the enumerations of subsets never show a single element. However, the inputs for the problem say that the array could be as small as a single element. So, what would be the answer in that case? Or consider a case where a single element is larger than all other possible elements combined: 100, -1, -1 In this case, if I count a single element as a subset the answer would be 100, but if it isn't, then the answer would be 99.

So, either a subset needs to include a single element. Or the constraints needs to change to say that 3 is the smallest length array possible.

Geez, people. I appreciate you trying to explain things, but let's be honest: you won't be able to explain it better than 1000 blog posts or youtube videos found on the internets. If the algorithm has a name, please use it. That's what helps more.

This HR problem is a small variation of something called Maximum subarray problem, of which its optimal algorithm is called Kadane's Algorithm. It's relatively simple. Everything is simple after you get it, I know - but this one is quite simple.

Kadane's algo deals with sub-arrays made of every element, but, if you look at other solutions, you'll see that it only needs a small change to work for the current HR problem.

Here's some links that helped:

• https://en.wikipedia.org/wiki/Maximum_subarray_problem
• https://www.youtube.com/watch?v=86CQq3pKSUw (I watched it 4 times. By the second watch, I was getting it.)

Be patient, pay attention and don't give up.

int incl = 0, excl = 0, temp;
for(int i = 0; i < arr.size(); i++) {
    temp = incl;
    incl = max(arr[i]+excl, temp);
    excl = temp;
}
return max(incl, excl);