1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Doi9t Jun 14 at 13:54
  • \$\begingroup\$ 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. \$\endgroup\$ – slepic Jun 15 at 4:47
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ That's a good point. didn't thought of cost associated with array copy. \$\endgroup\$ – Shashi Jun 15 at 4:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.