Maximum Non-Adjacent Sum

Difficulty: Medium · Pattern: Dynamic Programming · Concept: General Coding (DSA) — Core Patterns to Drill

Given a list of non-negative integers, find the maximum sum you can get by picking a subset of elements such that no two chosen elements are adjacent in the original list.

This is a canonical DP problem: at each position, you face a binary choice (take it or skip it), and today's optimal choice depends only on a small, fixed amount of information about what came before — the two ingredients of "overlapping subproblems + optimal substructure" the DSA prep page calls the hardest pattern to get comfortable with.

Your task: implement max_non_adjacent_sum(nums). Return 0 for an empty list.

Implement it yourself

assert max_non_adjacent_sum([]) == 0
assert max_non_adjacent_sum([5]) == 5
assert max_non_adjacent_sum([2, 4, 6, 2, 5]) == 13
assert max_non_adjacent_sum([3, 2]) == 3
assert max_non_adjacent_sum([1, 2, 3, 1]) == 4

Next: Longest Increasing Subsequence (a harder variant), or continue to The Lone Number