Problem Statement (Asked By Airbnb)

Given a list of integers, write a function to compute the largest sum of numbers such that no two numbers are adjacent in the list. The input may contain zero or negative values.

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.

Can you optimize your solution to run in O(N) time and use constant space?

Problem link: https://leetcode.com/problems/count-univalue-subtrees/description/

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

---

Solution:

This problem appears straightforward initially but contains some complexities. A greedy approach like picking the largest number, then the next largest non-adjacent number, and so on, doesn’t work consistently due to edge cases.

Instead, we can solve this problem recursively. Suppose we have a function that already computes the maximum sum of non-adjacent numbers for smaller arrays. Using this, we can decide between two cases:

1. Exclude the first element and compute the result for the subarray starting from the second element.
2. Include the first element and compute the result for the subarray starting from the third element.

Thus, the solution can be expressed as:

max(a[1:],a[0]+a[2:])

Approach 1: Recursive Solution (Inefficient, O(2^n)):

public class LargestNonAdjacentSum {
    public static int largestNonAdjacent(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {
            return Math.max(0, arr[0]);
        }
        return Math.max(
                largestNonAdjacent(java.util.Arrays.copyOfRange(arr, 1, arr.length)),
                arr[0] + largestNonAdjacent(java.util.Arrays.copyOfRange(arr, 2, arr.length))
        );
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 5, 10, 7};
        System.out.println("Max Sum: " + largestNonAdjacent(arr)); // Output: 15
    }
}

This recursive solution works but is highly inefficient due to redundant calculations.

Approach 2: Optimized Dynamic Programming Solution (O(n)):

We can use dynamic programming to avoid redundant calculations by storing the maximum sum of non-adjacent numbers up to each index in a cache.

public class LargestNonAdjacentSum {

    public static int largestNonAdjacent(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {
            return Math.max(0, arr[0]);
        }

        int[] cache = new int[arr.length];
        cache[0] = Math.max(0, arr[0]);
        cache[1] = Math.max(cache[0], arr[1]);

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

        return cache[arr.length - 1];
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 5, 10, 7};
        System.out.println("Max Sum: " + largestNonAdjacent(arr)); // Output: 15
    }
}

This solution runs in O(n) time but uses O(n) space.

Approach 3: Further Optimized Dynamic Programming (O(n) Time, O(1) Space):

Since we only need the last two values of the cache at any point, we can reduce the space complexity to O(1).

public class LargestNonAdjacentSum {

    public static int largestNonAdjacent(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {
            return Math.max(0, arr[0]);
        }

        int maxExcludingLast = Math.max(0, arr[0]);
        int maxIncludingLast = Math.max(maxExcludingLast, arr[1]);

        for (int i = 2; i < arr.length; i++) {
            int current = Math.max(maxIncludingLast, maxExcludingLast + arr[i]);
            maxExcludingLast = maxIncludingLast;
            maxIncludingLast = current;
        }

        return maxIncludingLast;
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 5, 10, 7};
        System.out.println("Max Sum: " + largestNonAdjacent(arr)); // Output: 15
    }
}

Explanation of Optimized Approach:

1. Base Cases:
   • For an empty array, the result is 0.
   • For a single-element array, the result is the maximum of 0 or the element itself.
2. Iterative Calculation:
   • maxExcludingLast: Stores the maximum sum excluding the current element.
   • maxIncludingLast: Stores the maximum sum including the current element.
   • For each element, update these values using the relation:

maxIncludingLast=max(maxIncludingLast,maxExcludingLast+current element)

Time Complexity: O(n)
Space Complexity: O(1)

---

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.