Maximum Sum of Non-Adjacent Elements

Question

Purpose

I recently came across an interview question that stumped me for a while

Given a list of integers, write a function that returns the largest sum of non-adjacent numbers.

I am looking for feedback around both my implementation and the correctness of my proposed solution (I have some test cases, but I could have missed a case).

Approach

For arrays with 1 or 2 values, the answer is trivial.

For arrays with more than 2 values, keep track of the maximum sum from the preceding non-adjacent elements that includes the most recent non-adjacent element, and the maximum sum from the preceding non-adjacent elements that excludes the most recent non-adjacent element.

So for [3, 1, 1, 5, 1] at index 3, the maximum sum from preceding non-adjacent elements that includes the most recent non-adjacent element is 1, while the maximum sum from preceding non-adjacent elements that excludes the most recent non-adjacent element is 3.

Taking the max of these two sums and adding them to the current value will produce the maximum sum for non-adjacent elements up to that index. Continuing this process for each remaining index and then comparing the last two calculated sums will produce the maximum sum.

Let's walk through this process with [3, 1, 1, 5, 1].

• At index 0, the max sum is 3
• At index 1, the max sum is 1
• At index 2, the max sum from including the most recent non-adjacent element is 3, while the max sum from excluding the most recent non-adjacent element is 0. Thus, we choose 3 and add that to the current value (1). 4 is now the max non-adjacent sum for index 2.
• At index 3, the max sum from including the most recent non-adjacent element is 1, while the max sum from excluding the most recent non-adjacent element is 3. Thus, we choose 3 and add that to the current value (5). 8 is now the max non-adjacent sum for index 3.
• At index 4, the max sum from including the most recent non-adjacent element is 4, while the max sum from excluding the most recent non-adjacent element is 3. Thus, we choose 4 and add that to the current value (1). 5 is now the max non-adjacent sum for index 4.
• The final two sums were 8 and 5 - we take the max (8).

Apologies if this was confusing to follow, it was difficult to describe my thought process.

Implementation

public class MaximumNonAdjacentElementSumIdentifier {
    public static int identify(int[] values) {
        if (values == null || values.length == 0) {
            throw new RuntimeException("Unable to identify sum");
        }

        if (values.length == 1) {
            return values[0];
        }

        int firstSum = 0;
        int secondSum = values[0];
        int previousValueSum = values[1];

        for (int i = 2; i < values.length; i++) {
            int value = values[i];
            int maximumCurrentElementSum = Math.max(firstSum, secondSum) + value;
            firstSum = Math.max(firstSum, secondSum);
            secondSum = previousValueSum;
            previousValueSum = maximumCurrentElementSum;
        }

        return Math.max(secondSum, previousValueSum);
    }
}

Answer 1

Variable names

firstSum and secondSum variable names aren't really descriptive of their purpose. Let's give them names according to the algorithm description:

int sumExcludingMostRecentNonAdjacentElement = 0;
int sumIncludindMostRecentNonAdjacentElement = values[0];
int sumUpToPreviousElement = values[1];

That's too verbose and it makes sense to remove common parts:

int excluding = 0;
int including = values[0];
int upToPrevious = values[1];

for (int i = 2; i < values.length; i++) {
    int value = values[i];
    int upToCurrent = Math.max(excluding, including) + values[i];
    excluding = Math.max(excluding, including);
    including = upToPrevious;
    upToPrevious = upToCurrent;
}

Negative numbers

The algorithm is based on the following assumption:

Taking the max of these two sums and adding them to the current value will produce the maximum sum for non-adjacent elements up to that index.

which doesn't take negative numbers into account:

• if both of these sums are negative they should not be added to the result;
• if the current value is negative it should not be added to the result.

To give an example, for the input 0, -1, -1 the method returns -1.

You can try to fix that by carefully keeping sums as positive and handling negative values:

int value = Math.max(values[i], 0);

You will also need to fix the initialization:

int including = Math.max(values[0],0);
int upToPrevious = Math.max(values[1], 0);

, and the trivial case:

if (values.length == 1) {
    return Math.max(values[0], 0);
}

As an alternative, you can replace negative elements with zeroes before processing.

Refactoring/understanding.

As far as I can see, the code should work correctly at this point. But both the algorithm description and the code are hard to follow with all these transitions:

int excluding = 0;
int including = Math.max(values[0], 0);
int upToPrevious = Math.max(values[1], 0);

for (int i = 2; i < values.length; i++) {
    int value = Math.max(values[i], 0);
    int upToCurrent = Math.max(excluding, including) + values[i];
    excluding = Math.max(excluding, including);
    including = upToPrevious;
    upToPrevious = upToCurrent;
}
return Math.max(including, upToPrevious);

Let's try to make code easier to understand step-by-step.

Currently, upToPrevious refers to the upToCurrent from the previous step. upToCurrent values for each iteration can be stored in an array, it saves us an assignment and hopefully helps us to derive a recurrence relationship between values:

int n = values.length;
//upToSums[i] refers to the upToCurrent value at the i-th step
int[] upToSums = new int[n];
upToSums[1] = Math.max(values[1], 0);
for (int i = 2; i < n; i++) {
    int value = Math.max(values[i], 0);
    upToSums[i] = Math.max(excluding, including) + value;
    excluding = Math.max(excluding, including);
    including = upToSums[i-1];
}
return Math.max(including, upToSums[n-1]);

Turns out, including referes upToSums[i-1] from the previous step, we can replace it with upToSums[i-2]:

upToSums[0] = Math.max(values[0], 0);
upToSums[1] = Math.max(values[1], 0);
for (int i = 2; i < n; i++) {
    int value = Math.max(values[i], 0);
    upToSums[i] = Math.max(excluding, upToSums[i-2]) + value;
    excluding = Math.max(excluding, upToSums[i-2]);
}
return Math.max(upToSums[n-2], upToSums[n-1]);

Now it's easier to see what's going on with excluding:

• At step 2 excluding is 0.
• At every other step excluding is the maximal element of upToSums from 0 to i-3.

Let's define an array for the maximum value of upToSums and calculate excluding based on that:

int[] maxSums = new int[n];
for (int i = 2; i < n; i++) {
    int value = Math.max(values[i], 0);
    int excluding = i==2 ? 0 : maxSums[i-3];
    upToSums[i] = Math.max(excluding, upToSums[i-2]) + value;
    maxSums[i-2] = Math.max(excluding, upToSums[i-2]);
}

This code still vaguely follows your algorithm description as "maximum sum from the preceding non-adjacent elements that excludes the most recent non-adjacent element" is somewhat equivalent to "maximum sum of non-adjacent elements for the sequence with the last three elements removed".

Notice, that maxSums[i-2] is calculated twice. We can reuse the result by changing the order of calculations:

    int value = Math.max(values[i], 0);   
    maxSums[i-2] = Math.max(i==2 ? 0 : maxSums[i-3], upToSums[i-2]);    
    upToSums[i] = maxSums[i-2]+ value;   

It's weird that maxSums[i-2] is calculated at the i-th step. We can define starting values and calculate maxSums[i] right after upToSums[i]:

int[] maxSums = new int[n];
maxSums[0] = upToSums[0];
maxSums[1] = Math.max(upToSums[0], upToSums[1]);
for (int i = 2; i < n; i++) {
    int value = Math.max(values[i], 0);
    upToSums[i] = maxSums[i-2]+ value;  
    maxSums[i] = Math.max(maxSums[i-1], upToSums[i]);
}

Also, we can use maxSums to return the result as the maximum is already calculated:

//maximal sum is already calculated
return maxSums[n-1];

Code so far (without trivial cases):

int n = values.length;
int[] upToSums = new int[n];
upToSums[0] = Math.max(values[0], 0);
upToSums[1] = Math.max(values[1], 0);
int[] maxSums = new int[n];
maxSums[0] = upToSums[0];
maxSums[1] = Math.max(upToSums[0], upToSums[1]);
for (int i = 2; i < n; i++) {
    int value = Math.max(values[i], 0);
    upToSums[i] = maxSums[i-2]+ value;  
    maxSums[i] = Math.max(maxSums[i-1], upToSums[i]);
}
return maxSums[n-1];

At this point upToSums is never used and can be eliminated:

int n = values.length;
int[] maxSums = new int[n];
maxSums[0] = Math.max(values[0], 0);
maxSums[1] = Math.max(Math.max(values[1], 0), maxSums[0]);
for (int i = 2; i < n; i++) {
    int value = Math.max(values[i], 0);
    maxSums[i] = Math.max(maxSums[i-1], maxSums[i-2]+ value);
}
return maxSums[n-1];

At last we also separate the handling of negative numbers from the main algorithm that will work with an array of non-negative numbers:

//replacing negative values with 0
int n = values.length;
for(int i=0; i<n; i++) {
    if(values[i]<0) {
        values[i] = 0;
    } 
}

//trivial case
if(n==0) {
    return values[0];
} 

int[] maxSums = new int[n];
maxSums[0] = values[0];
maxSums[1] = Math.max(values[1], values[0]);
for (int i = 2; i < n; i++) {
    maxSums[i] = Math.max(maxSums[i-1], maxSums[i-2]+ values[i]);
}
return maxSums[n-1];    

This code is logically equivalent to the previous version, but it's easier to follow. Actually, the main part of the algorithm (recursive formula) is written in the code itself:

The largest sum of non-adjacent elements (maxSums(i)) for the first i elements of the list of non-negative numbers a is defined using the recurrence
maxSums(i) = max(maxSums(i-1), maxSums(i-2)+a[i])
with initial conditions:
maxSums(0) = a[0]
maxSums(1) = max(a[0], a[1])

Sum of zero elements

In its current form, the algorithm will return 0 for the list of negative numbers. This may or may not be acceptable, as the question doesn't state that the sum should contain at least one element. You'll need to clarify the particular requirements with your interviewer and, if necessary, write the code to detect this special case.