Given a list of non-negative numbers, return the maximum sum of a subset with no two chosen elements adjacent in the list.
nonAdjacentSum(nums)
Input format: space-separated integers (may be empty → 0).
[2, 7, 9, 3, 1] // → 12 (2 + 9 + 1)
[7, 7, 7, 7] // → 14 (7 + 7)
[5] // → 5
At each position, one binary choice: include it, or don't. Including it means the best from here is this element's value plus the best starting two positions later (adjacency forbids the very next one). Skipping it means the best from here is whatever's achievable starting at the next position. The overall best is the larger of the two.
Once the starting position runs past the end, nothing's left to take — best is 0.
Different take/skip sequences land on the same starting position later — skipping twice, or taking-then-forced-skip, can both arrive at the same index. The naive version treats each arrival as fresh, recomputing the best from that position every time even though it never depends on history. This branches exponentially with the list's length.
The best sum from a given index depends only on that index and what's after it — not on earlier take/skip decisions. Cache from index to best sum from there onward. Check before recursing; otherwise compute the max of "take here plus best from two ahead" and "skip to one ahead," store, return.
Only as many distinct indices as elements exist, so total work is O(n) instead of exponential. "Take it and jump ahead, or skip it and move on by one, cache by index" is one of the most common DP shapes — house robbing, non-overlapping job scheduling, picking non-adjacent items under constraints.
def non_adjacent_sum(nums):
memo = {}
def best(i):
if i >= len(nums):
return 0
if i in memo:
return memo[i]
v = max(nums[i] + best(i + 2), best(i + 1))
memo[i] = v
return v
return best(0)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.