Maximum subset sum with no adjacent elements

Question

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(
      array[0] + maxSubsetSumNoAdjacent(Arrays.copyOfRange(array, 2, array.length)),
      array[1] + maxSubsetSumNoAdjacent(Arrays.copyOfRange(array, 3, array.length))
  );
}

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.

Answer 1

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)),
  array[1] + maxSubsetSumNoAdjacent(Arrays.copyOfRange(array, 3, 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. 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.

Note that recursive calls that pass array plus a starting index will never copy the array. They merely pass a pointer to start of original array, in O(1) time, independent of how enormous that array happens to be.

You have an opportunity to dramatically improve the implemented algorithm, by passing index to the "as yet unsolved" portion of the array.