Pattern visualizer
Max Sum of Non-Adjacent Elements
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. Animated on: nums = [2, 4, 6, 2, 5] — find the maximum sum of elements with no two chosen elements adjacent in the array..
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
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