Maximum sum of non adjacent elements
MediumTake it and skip one, or skip it
Problem
Return the maximum sum of a subsequence with no two chosen elements adjacent.
At each house choose: skip it (keep the best so far) or rob it plus the best from two houses back.
The idea
At each element choose between including it plus the best from two positions back, or excluding it and keeping the best from one position back. That single decision is the house-robber recurrence.
The trick
- dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
- Two rolling variables suffice — O(1) space.
- Clamp at zero if empty subsequences are allowed.
Step 1 of 7. Brute force: pick(5) calls pick(4) and pick(3) — and each of those splits again. calls 1.
Exponential tree.
1function pick(i) {2 if (i < 0) return 0;3 return Math.max(pick(i - 1), pick(i - 2) + nums[i]);4}Input
- nodes
- 1, 0 edges
Memory
- calls
- 1
- pick(1) redone
- —
- brute calls
- —
Call stack
- 0visit(pick(5))
Output
- with memo
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 3, 1]
- Output:
- 4
- Explanation:
- Rob houses 1 and 3 → 1 + 3 = 4.
Example 2
- Input:
- nums = [2, 7, 9, 3, 1]
- Output:
- 12
- Explanation:
- Rob 2 + 9 + 1 = 12.
Example 3
- Input:
- nums = [5]
- Output:
- 5
- Explanation:
- One house → just take it.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.