[Java] Maximum sum of non adjacent numbers in array

Given an array of integers, containing zeros, negative values and duplicates, find the maximum sum that can be generated by picking non adjacent elements.

Since it's a sum, we need at least two operands, therefore we need at least 3 elements in our array.

If our array was made only of negative numbers, then the problem becomes finding the couple of non adjacent biggest negative numbers, that is ONLY two numbers. Therefore in that case, the logic is incompatible with the one to solve for positive numbers as we want to add MULTIPLE numbers in that case.

We will therefore treat negative elements in our array as value 0 to make them not an interesting pick for our logic and therefore skip over them. The problem definition itself suggests how to solve it, given the triple:

(1) sum of previous elements excluding last: this sum excluded element in position current - 1

(2) sum of previous elements including last: this sum included element in position current - 1

(3) current element

should we choose (1) + (3) or (2)?

And we repeat this question for each element in our input. As for the base case, we've already seen that we need at least 3 elements to produce a valid answer, which in case of exactly 3 elements is simply first + last, no matter which value was in second place.

So our logic makes sense starting from element in position 2. What values we set for elements in position 0 and 1?

position 0: would be the choice for elements coming at a non existing index -1 and -2, we set it to first element in our array

position 1: would be the choice of keeping element in position 0 or adding ourselves to element in non existing index -1, we therefore pick the maximum between ourselves and the element in position 0

At the end, we simply look at the two sums and pick the biggest.

You can check my implementation of maxSumNonAdjacentElements on my Gist along with some tests in MaxSumNonAdjacentElementsJTests.