Given a list of integers, write a function that returns the largest sum of non-adjacent numbers? Numbers can be 0 or negative

Question

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

For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.

Follow-up: Can you do this in O(N) time and constant space?

class DailyCodingProblem9 {

    public static void main(String args[]) {

        int arr[] = { 2, 4, 6, 2, 5, 13 };
        int res = solution(arr);
        System.out.println(res);

        int arr1[] = { 1, 0, 3, 9, 2, 14 };
        res = solution(arr1);
        System.out.println(res);
    }

    static int solution(int[] arr) {
        int n = arr.length;
        int[] maxArr = new int[n];
        int max = 0;
        for (int i = n - 1; i > 0; i--) {
            maxArr[i] = findLargestSum(arr, i, n, maxArr);
            max = Math.max(max, maxArr[i]);
        }
        return max;

    }

    static int findLargestSum(int[] arr, int i, int n, int[] max) {
        System.out.println(i);
        if (max[i] != 0) {
            return max[i];
        }
        if (i == 0 || i == 1) {
            return arr[i];
        }
        if (i - 2 == 0) {
            return arr[i] + findLargestSum(arr, i - 2, n, max);
        }
        return arr[i] + Integer.max(findLargestSum(arr, i - 2, n, max), findLargestSum(arr, i - 3, n, max));

    }

}

How do I solve it in constant space? I found an answer here, but could not understand the logic.

Answer 1

What you implemented is the recursive solution:

sum(k)
  | k < 0 = 0
  | otherwise = max( sum(k-1), sum(k-2) + arr[k] )

You can also implement it iteratively using an O(n) extra space:

sum = int[n]
sum[0] = max(      0, arr[0] )
sum[1] = max( sum[0], arr[1] )
for (int k = 2; k < n; k++)
{
    sum[k] = max( sum[k-1], sum[k-2] + arr[k] )
}

You may notice that nothing but the two rightmost values will ever be used in the next iteration. We can get rid of the array entirely and store only those values instead, which leads to O(1) space usage.

s2 = max(  0, arr[0] )
s1 = max( s2, arr[1] )
for (int k = 2; k < n; k++)
{
    s0 = max( s1, s2 + arr[k] )
    s2 = s1
    s1 = s0
}

Answer 2

Quick note first:

The post you link to only allows for positive numbers in input (with 0 also counting as possitive). Their proposed solution does work with a small adaptation that replaces any negative number with a 0 instead (where you just don't include the negative number in the maximum sum).

For example: The result is the same for arrays [1,0,-1,0,1] and [1,0,0,0,1].

---

Asking us to write a different solution or asking how someone elses code works is off topic here. Instead I'll try to just provide some hints on how to get started on the constant space solution.

DISCLAIMER: None of the following code is tested. Copy at own risk (also indices in array are probably weird / inconsistent)

Let us consider a different question first that can be solved with a really similar strategy. Namely finding the n-th number of the really well known fibonaci sequence.

The most obvious solution is using recursion to calculate the previous 2 steps:

private static int recursiveFib(int n){
    if(n<2){
        return 1;
    }

    return recursiveFib(n-2)+recursiveFib(n-1);
}

The problem with this solution is that it will do the same calculations for smaller numbers over and over. You already recognised this and used an array to store intermediate results. That way you only need to calculate each number only once.

private static int recursiveFibMemorised(int n){
    return recursiveFibMemorised(n, new int[n]);
}

private static int recursiveFibMemorised(int n, int[] known){
    if(n<2){
        return 1;
    }
    if(known[n]==0){
        known[n] = recursiveFibMemorised(n-1, known) + recursiveFibMemorised(n-2,known);
    }
    return known[n];
}

The only problem left here is the recursive call itself. If we're smarter and start calculation from number 0 upwards we can guarantee that any previous ones are already stored. So instead of the recursive call we can directly look those up from the known array instead:

private static int recursiveFibMemorised2(int n){
    int[] known = new int[n+1];
    for(int i = 0; i<n; i++){
        recursiveFibMemorised2(n, known);
    }
    return known[n];
}

private static int recursiveFibMemorised(int n, int[] known){
    if(n<2){
        return 1;
    }
    if(known[n]==0){
        known[n] = known[n-1] + known[n-2];
    }
    return known[n];
}

Now that we got rid of the recursive call this looks kinda silly, so let's just do the calculation inside the loop directly instead:

private static int recursiveFibMemorised2(int n){
    if(n<2) return 1;

    int[] known = new int[n+1];
    known[0]=1;
    known[1]=1;
    for(int i = 0; i<n; i++){
        known[i]=known[i-1] + known[i-2];
    }
    return known[n];
}

Finally you can see that we only ever access the known array with the last 2 indices. Any previous value could be discarded. So let's use 2 ints instead of an entire array:

private static int optimisedFib(int n){
    if(n<2){
        return 1;
    }
    int prev2 = 1;
    int prev1 = 1;
    int current = 2;
    for(int i = 2; i <= n ; i++){
        current = prev2 + prev1;
        prev2 = prev1;
        prev1 = current;
    }
    return current;
}

---

A really similar strategy can now be used for your original problem. The most important thing to see is how to use a previously know max sum of a sub array. Take for example the array [5,1,1,4]. If we first calculate the max sum of the subarray [5,1]. This is 5. Than at the 4th element we can calculate the maximum as 4 + result of [5,1] -> 9.

Notice that we're not interested in the value of the second element anymore there. Only in the max at that point. This means that we want to always store either the maximum value of the subarray 2 elements before + the current value; OR the maximum sum up to 1 element before but without adding the current element since it's adjacent.