# 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;
else if (array.length == 2) return Math.max(array, array);

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. – Doi9t 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. – slepic 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 + 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.