DSA Crash Course [Part 79] - Non Adjacent Sum Approach

In this lesson, Alvin explores the strategy to solving the following interview problem:

Write a function, non_adjacent_sum, that takes in a list of numbers as an argument. The function should return the maximum sum of non-adjacent items in the list. There is no limit on how many items can be taken into the sum as long as they are not adjacent.

For example, given: [2, 4, 5, 12, 7]

The maximum non-adjacent sum is 16, because 4 + 12. 4 and 12 are not adjacent in the list.

nums = [2, 4, 5, 12, 7]
non_adjacent_sum(nums) # -> 16

nums = [7, 5, 5, 12]
non_adjacent_sum(nums) # -> 19

nums = [7, 5, 5, 12, 17, 29]
non_adjacent_sum(nums) # -> 48

nums = [
72, 62, 10,  6, 20, 19, 42,
46, 24, 78, 30, 41, 75, 38,
23, 28, 66, 55, 12, 17, 9,
12, 3, 1, 19, 30, 50, 20
]

non_adjacent_sum(nums) # -> 488

If you need additional support taking these DSA skills and actually applying them, take Alvin's complete data structures and algorithms course on Structy. You can try out the concepts yourself in their interactive code editor and learn advanced DSA patterns like stack exhaustive recursion.

Use this link to get 20% off the entire Structy DSA learning experience.

Follow Alvin on LinkedIn: https://www.linkedin.com/in/alvin-zablan-b73a92117/