Max Subset Sum No Adjacent

Category: Dynamic Programming

Difficulty: Medium

Description

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

If the input array is empty, the function should return 0.

Sample Input

array = [75, 105, 120, 75, 90, 135]

Sample Output

330 // 75 + 120 + 135

Optimal Space & Time Complexity

O(n) time | O(1) space - where n is the length of the input array