As you may know, one of our blog’s current focuses is on Uber interview questions. Their questions are usually representative and you can expect exactly the same kind of questions from other top companies like Google, Facebook, Airbnb, etc.. In addition, we only cover questions that were asked recently. This week, the question is maximum sum of non-adjacent elements. It’s of medium difficulty, you may expect to have it as the second question in an on-site interview. We are going to cover topics including array, recursion/dynamic programming, algorithm efficiency and so on so forth.

## Maximum Sum of Non-adjacent Elements

Given an array of integers, find a maximum sum of non-adjacent elements.

For example, inputs [1, 0, 3, 9, 2] should return 10 (1 + 9).

The question has been asked by Uber recently (as the time of writing). I’ve also seen many similar questions like finding the maximum sum of subarrays.

## Analysis

Again, if you haven’t seen this questions before, solve it by yourself first. Otherwise, there’s no point to reading this post.

It’s not obvious to solve this problem naively. Unlike many other interview questions, you can hardly use brute force or some greedy algorithms here, because there’s no way for you to list all non-adjacent elements combination.

But just because of this, it provides a great hint – dynamic programming. Let me explain more here.

## Dynamic programming

You may check Step by Step Guide to Dynamic Programming if you are unfamiliar with this concept and it’s completely necessary to know it for coding interviews.

When I was trying to solve this problem, there are two obvious things that make me think about dynamic programming.

First, __when the question is about finding particular subarrays or subsets, dynamic programming is usually a great approach.__ This is because the problem is easy to break down into sub-problems.

Second, __when you find it impossible to brute force all possibilities, it also indicates that recursion or dynamic programming is worth to try.__ For example, finding subarray with given sum can easily be solved by brute force (of course it’s not optimal), but you can do the same thing to find the subset with given sum. (Check this post for more info)

## Solution

With that in mind, we should think about how to break down the big problem into sub-problems.

Suppose we know the max sum for all subarrays, how can it help us to solve the overall problem? Let’s use **max_sum[i]** denote the maximum sum for subarray **arr[0…i]**. If the last number **arr[i] **is included in the sum, **max_sum[i]** should equal to **arr[i] + max_sum[i-2] **(because **arr[i-1]** cannot be included). Similarly, if **arr[i] **isn’t included, then **max_sum[i]** should equal to **arr[i-1]**.

Therefore, we have the following formula:

**max_sum[i] = MAX(arr[i] + max_sum[i-2], max_sum[i-1])**

So the code is like:

## Memorization

One of the advantages of dynamic programming is memorization. In the above code, many steps are unnecessarily re-calculated. To make it faster, we should store all results in memory. Thus, we have the following code:

As you can see, we use array **mem **to store all results we’ve processed so that we won’t repeat the unnecessary calculation. The time complexity is O(N) because from i = 0 to N, every single one is calculated at most once due to memorization. As we use an extra array, the space complexity is O(N) as well.

## Optimization

Can you further optimize the solution?

First of all, there’s no way to improve the time complexity because we should check every single number at least once. Thus O(N) is the lower bound. Thus, we should think about reducing memory usage.

If you take a look at the previous formula again, you might notice one interesting fact. Every step only relies on the previous two steps results. In other words, if we care about **max_sum(i)**, there’s no need to store anything before i-2.

The code might be quite different from previous versions, that is because we are doing a bottom-up approach for dynamic programming. We use **prevOne **and **prevTwo **to store results of previous two steps. From i = 0 to N, we store the results of each subarray **arr[0…i] **to **prevOne** and **arr[0…i-1] **to **prevTwo**, thus the next iteration can use them to calculate for the new subarray. In essence, they are exactly the same as previous solutions.

## Summary

I hope you found the question maximum sum of non-adjacent elements helpful. Instead of giving you the final solution, I think it’s very necessary to provide the whole analysis process and provide the coding solution at each step. Otherwise, many people won’t be able to know where the final solution come from.

Dynamic programming is a hard topic in coding interviews. Most of the time a top-down approach is enough, but for this one, a bottom-up approach is more efficient.

By the way, if you want to have more guidance from experienced interviewers, you can check Gainlo that allows you to have mock interview with engineers from Google, Facebook ,etc..

The post is written by
**
Gainlo** - a platform that allows you to have mock interviews with employees from Google, Amazon etc..

I'd like to learn more

The Memorization and Optimization pictures show up as blank

The image of last to code snipet is showing forbidden, kindly check it.

Thanks for posting this! Great stuff!

I don’t know if it is just me or what, but almost every time I check a recent article, for the first few days all the code images are broken. Is it a well known issue or something?

“Similarly, if arr[i] isn’t included, then max_sum[i] should equal to arr[i-1].” -> Shouldn’t it be max_sum[i-1] instead of arr[i-1]?

This is an easy interview question to brute force for an 0(1) space complexity (albeit at an o(n^2) time cost):

int bestSum = 0;

for (int i = 0; i<array.size(); i++)

{

for (int j = 0; j sum)

{

sum = array[i] + array[j]

}

}

}

OK, since the pseudo code I wrote doesn’t display properly:

Easy to brute force for O(1) space and O(n^2) time complexity.

Loop through everything in the given array twice.

– if i – j is 0, you know that you’re looking at yourself so ignore.

– If the absolute value of i – j is 1, you know that the numbers are next to each other so ignore.

– in all other cases, compare (array[i] + array [j]) to a running total sum value, if higher then update the sum value.

This solution does not work. For input [1, 0, 3, 9, 2, 9, 10], it returns 20 when it should return 19.

Oops, nevermind. I misinterpreted the question.

20 is correct, 1 + 9 + 10

Another approach. The maximum sum has to be in the top 4. If 1st and 2nd are non adjacent that is your answer. Similary if 1st and 2nd are adjacent but 3rd is not. 1st and 3rd is your answer. Finally if 2nd and 3rd are adjacent max(1st and 4th, 2nd and 3rd) is your answer.

I’m not a native English speaker, but I think it’s called memoization.

This solution won’t work if negative numbers are allowed.

For example:

a = [-1, -1, 3, 9, 2] will return 8.

We can fix this by taking max( arr[i], oneBack, twoBack + arr[i] )