Interview Questions — Maximizing Sum of Non-Adjacent Elements in an Array

Photo by Antoine Dautry on Unsplash

Write a JavaScript function that calculates the maximum sum achievable by selecting non-adjacent elements from a given array of integers, which may include zero or negative numbers.

For instance, if the input array is [3, 7, 4, 6, 5], the function should return 13, because the optimal selection is 3, 4, and 6. In another case, with an array like [2, 10, 3, 4, 5], the function should output 15, achieved by choosing 10 and 5.

The solution should be optimized to run in O(N) time complexity and require constant space.

Solution

To solve this problem, we will develop a JavaScript function to find the maximum sum possible by selecting non-adjacent elements from an array of integers. This problem can be approached efficiently using dynamic programming principles, ensuring that the solution runs in O(N) time complexity, where N is the number of elements in the input array. The key to solving this problem with constant space is to track two variables throughout the iteration of the array:

1. Include: This variable tracks the maximum sum that includes the current element.
2. Exclude: This variable keeps track of the maximum sum that excludes the current element.

As we iterate through the array, we have two choices for each aspect: either to include the current component of our sum or exclude it. If we include it, the new sum (include) becomes the previous exclude plus the current element (since we cannot select adjacent elements). If we exclude it, the new sum (exclude) becomes the maximum of the previous include and exclude. This ensures we always have the optimal sum to the current index without violating the non-adjacency constraint.

function maxSumOfNonAdjacent(arr) {
    let include = 0; // Maximum sum including the current element
    let exclude = 0; // Maximum sum excluding the current element
    for (let num of arr) {
        // Temporary store the current state of exclude
        let temp = exclude;
        // Update exclude to the maximum of exclude and include
        exclude = Math.max(include, exclude);
        // Update include to the new sum formed by adding the current element
        // to the maximum sum excluding the previous element
        include = temp + num;
    }
    // The maximum sum of non-adjacent elements is the max of include and exclude
    return Math.max(include, exclude);
}
// Test cases
console.log(maxSumOfNonAdjacent([3, 7, 4, 6, 5])); // Outputs: 13 (3 + 4 + 6)
console.log(maxSumOfNonAdjacent([2, 10, 3, 4, 5])); // Outputs: 15 (10 + 5)

Explanation:

• For the first example [3, 7, 4, 6, 5], the function correctly calculates the maximum sum as 13 by selecting elements 3, 4, and 6. Note that these elements are non-adjacent.
• In the second example [2, 10, 3, 4, 5], the optimal sum is 15, achieved by selecting 10 and 5.

This approach ensures that we make an optimal decision at each element by considering the history of our choices in a manner that respects the problem’s constraints while maintaining a linear time complexity and constant space usage.

Follow me on Instagram, Facebook or Twitter if you like to keep posted about tutorials, tips and experiences from my side.

You can support me from Patreon, Github Sponsors, Ko-fi or Buy me a coffee