Write a function that takes in an array of positive integers and returns the maximum sum of non-adjacent elements in the array.
If the input array is empty, the function should return 0.
Sample input
[75, 105, 120, 75, 90, 135]
Sample output
330 = 75 + 120 + 135
Solution
Time Complexity: O(n)
Space Complexity: O(1)
static int maxSubsetSumNoAdjacent(int[] array) {
int answer = 0;
if (array.length == 0) {
return 0;
} else if (array.length == 1) {
return array[0];
}
int first = Math.max(array[0], array[1]);
int second = array[0];
int current = 0;
for (int i = 2; i < array.length; i++) {
current = Math.max(first, second + array[i]);
second = first;
first = current;
}
answer = first;
return answer;
}