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.
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 '20 at 13:54