# Maximum subset sum with no adjacent elements

Posted on

Problem

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.

Solution

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 pair of copy statements is wasteful.
You’re allocating temp storage (for GC to collect)
and consuming memory bandwidth.
It turns what could be a linear algorithm into a quadratic one (O(n) → O(n^2)).

The caller is going to simply hand you an array,
so you have to conform to that public API, accepting a single argument.
from index `0` onward to end of array.