Max Subset Sum No Adjacent in JavaScript

The Prompt

Create a function that takes an array of positive integers and returns the maximum sum of the non-adjacent elements in the array.

If the input array happens to be empty, return a 0.

The Code

First, let’s create a template for the function.

Now, to handle an edge case provided by the prompt, if the input array is empty, then the function must return 0. This can be handled with a simple (if) statement.

And since we’re taking care of edge cases… what if there was only one element in the input array? The sum would be the value of that one element. We can handle this with another (if) statement.

After handling those edge cases, let’s proceed with creating the function.

We’ll create a copy of the input array and manipulate it instead of the input.

Following, we’ll set the element at index [1] to the max of the first or second element in the input array. (This will let us know which element to start counting from, since we want the max sum of adjacent numbers, it has to be the largest number between the first two elements in the input array).

Next, we’ll initiate a for loop to traverse maxSums, from index [2].

And we’ll set the element in position [i] of maxSums, to the max of the following elements:

• The element in position -> maxSums[i -1]
• The element in position -> maxSums[i -2] + array[i]

Almost done!

Now, we just need to return the final element of maxSums. At this point, after coming out of the for loop, the final element will be the final element.

The final code should look like the following:

Complexity Analysis

The time complexity of this function is O(n) time, where (n) represents the length of the input array.

The space complexity of this function is also O(n) time, where (n) represents the length of the copied array (maxSums).