Largest sum of non-adjacent numbers

Tags:

Given an array of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.For example,

Input:
[2, 4, 6, 2, 5] 
Output:
13
Explanation:
Since we pick 2, 6, and 5. 

Input:
[5, 1, 1, 5] 
Output:
10 
Explanation:
Since we pick 5 and 5.

Thought process

This problem is very similar to the coin change problem, where for each coin we make a decision, whether to include or exclude a coin in the change or not.

In this problem as well, we make the choice for each number. What if we include a number at index i in the sum and what if we do not include it? If we include the number in the sum, which eventually may be the maximum sum, what can we do with the remaining numbers in the array? If we include a[i], then we definitely cannot include a[i+1], due to the constraint of non-adjacent numbers. After making the choice that we will include a[i] into the sum, our problem reduces to find the maximum sum of non-adjacent numbers from index i+2 to a.length-1.

What if I do not include this number a[i] in the sum? In that case, we can choose a[i+1] in the sum, so the problem reduces to find the largest sum of non-adjacent numbers in the array from index i+1 to a.length

We do not know which choice (to include or exclude a[i]) will give us the largest sum, so we try both and take the maximum of both.

Recursive implementation

    public int sum(int[] a){
        return sumUtil(a,0);
    }

    private int sumUtil(int[] a, int index){
        if(index > a.length-1){
            return 0;
        }

        return Math.max(a[index] + sumUtil(a, index+2),
                    sumUtil(a, index+1)
        );
    }

For each number we take two choices and follow them, overall complexity of above implementation is O(2n) where n is the length of the array.
Let’s see the execution tree of the recursive implementation with one of the examples, it looks like this:

largest sum of non adjacent numbers

It is evident from the execution tree that there are many subproblems colored red, blue, and light blue as groups, which are solved again and again. This is called overlapping subproblems and is a necessary condition to think in dynamic programming terms. We already know that an optimal solution to subproblem leads to an optimal solution to the original problem, hence, we can apply the dynamic programming approach here.

The best way to avoid calculating subproblems, again and again, is to memorize what is already calculated, so let’s modify the code to use a cache, this approach is called a top-down approach.

Top down implementation

    public int sum(int[] a){
        int [] cache = new int[a.length];
        return sumUtil(a,0, cache);
    }

    private int sumUtil(int[] a, int index){
        if(index > a.length-1){
            return 0;
        }
        if (cache[index] > 0){
            return cache[index];
        }

        cache[index] = Math.max(a[index] + sumUtil(a, index+2),
                    sumUtil(a, index+1)
        );
        return cache[index];
    }

There will be a maximum n calls to the sumUtil() function, so time complexity reduces to O(n) along space complexity of O(n).

How can we implement the bottom-up solution for this problem? If we defined a 1D array dp[] where dp[i] represents the maximum sum which can be achieved till index i of array. To include a[i] into that sum, we have to look for maximum sum that can be achieved till index i-2 i.e dp[i-2]. If we exclude the index, then we get the maximum sum till index i-1 i.e dp[i-1]. We take whatever is the maximum.
Recurrece relation is as follows.

dp[i] = max(dp[i-2] + a[i], dp[i-1]);

Bottom up implementation

   private int sumDP(int[] a){
        if(a.length == 0) return 0;

        if(a.length == 1) return a[0];
        if(a.length == 2) return Math.max(a[0], a[1]);

        int [] dp = new int[a.length];

        dp[0] = a[0];
        dp[1] = Math.max(a[0], a[1]);

        int max = 0;
        for(int i=2; i<a.length; i++){
            dp[i] = Math.max(a[i] + dp[i-2], dp[i-1]);
            max = Math.max(max, dp[i]);
        }

        return max;
    }

The time complexity of bottom-up approach is also O(n) along space complexity of O(n).

Follow-up: Can you do this in constant space?