# Maximum subset sum with no adjacent elements

Write a function that takes an array of integers (Both Positive and negative) and return the maximum sum of non adjacent elements. Note that even if all values are negative, I don't have an option to choose empty subset and return sum as 0.

Recursive solution that I wrote:

public static int maxSubsetSumNoAdjacent(int[] array) {
if (array.length == 0) return 0;
else if (array.length == 1) return array[0];
else if (array.length == 2) return Math.max(array[0], array[1]);

return Math.max(
);
}


The recursive solution works. I've tried an iterative solution, but that didn't work.

Test cases

Positive Numbers:

75, 105, 120, 75, 90, 135
Ans : 330 (75 + 120 + 135)

Negative Numbers:

-1, -10, -10, -1, -2
Ans: -2 (-1 + -1)

I'd like a review of the code provided.

• But the iterative solution does not work for negative numbers Hello, the second snippet is off-topic, since the code is not working as intended; I suggest that you read the What topics can I ask about here? Code Review aims to help improve working code. If you are trying to figure out why your program crashes or produces a wrong result, ask on Stack Overflow instead. Code Review is also not the place to ask for implementing new features. Jun 14 '20 at 13:54
• You said you cannot choose empty subset. But in your negative numbers example you dont choose 1 element subset either. Shouldn't the answer be -1? Or effectively minimum input size is 3? But that doesnt seem to correspond with your code, where you return greater of the two elements if array length is 2. Jun 15 '20 at 4:47

Many folks find that tacking on { } braces to even a single-line if body is a useful way of preventing future bugs.

You wrote:

  array[0] + maxSubsetSumNoAdjacent(Arrays.copyOfRange(array, 2, array.length)),

The caller is going to simply hand you an array, so you have to conform to that public API, accepting a single argument. But nothing stops you from overloading, from writing a private helper. Your public function should immediately ask the helper about the array, from index 0 onward to end of array. Then all the work happens in the helper.