Max Sum of Non-Adjacent Elements
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
At every index there are only two possibilities: skip it, in which case the best sum is whatever the previous index already achieved, or take it, in which case its neighbour is forbidden so the best sum is two indices back plus this value. dp[i] is just the better of those two, which makes the whole array collapse into one left-to-right pass with no branching search needed.
Details
Animated on: nums = [2, 4, 6, 2, 5] — find the maximum sum of elements with no two chosen elements adjacent in the array.
Problem:Max Sum of Non-Adjacent ElementsMedium
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
step 1 / 6
dp over [2, 4, 6, 2, 5] — dp[i] = best non-adjacent sum using nums[0..i]
dp[0] = nums[0] = 2: with only one element there is nothing to skip, so taking it is the only choice.
1FUNCTION maxSumNonAdjacent(nums):2 n <- LENGTH(nums)3 dp[0] <- nums[0]4 dp[1] <- MAX(nums[0], nums[1])5 FOR i FROM 2 TO n - 1:6 dp[i] <- MAX(dp[i-1], dp[i-2] + nums[i])7 RETURN dp[n-1]
← / → step · space play · Home restart
Every step in words
Show all 6 steps
- dp[0] = nums[0] = 2: with only one element there is nothing to skip, so taking it is the only choice.
- dp[1] = max(nums[0], nums[1]) = max(2, 4) = 4: nums[0] and nums[1] are adjacent, so at most one of them can be picked.
- dp[2] = max(dp[1]=4, dp[0]+nums[2]=2+6=8) = 8: adding nums[2]=6 to dp[0] beats skipping it, so index 2 joins the picked set.
- dp[3] = max(dp[2]=8, dp[1]+nums[3]=4+2=6) = 8: nums[3]=2 isn't worth taking here, so dp[3] just carries dp[2] forward.
- dp[4] = max(dp[3]=8, dp[2]+nums[4]=8+5=13) = 13: adding nums[4]=5 to dp[2] beats skipping it, so index 4 joins the picked set.
- dp[4] = 13 — the best sum of non-adjacent elements in [2, 4, 6, 2, 5] is 13.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.