Maximum sum such that no two elements are adjacent (House Robber)
Problem
Pick elements of the array so that no two chosen elements are adjacent, maximising their sum. In House Robber the values are money in houses along a street.
Example 1
Input: [2, 7, 9, 3, 1] Output: 12
2 + 9 + 1.
Also asked as: maximum sum such that no 2 elements are adjacent · House Robber · Maximum sum such that no two are adjacent
Test cases
Case 1
Input: [2,7,9,3,1] Expected: 12
Case 2
Input: [1,2,3,1] Expected: 4
Case 3
Input: [5] Expected: 5
View solutionHide solution1 approach
1. Pick / skip DP, O(1) space
Time O(n)Space O(1)
best[i] = max(best[i-1], best[i-2] + a[i]) — either skip element i or take it and add the best up to i-2.
function maxNonAdjacentSum(a) { let incl = 0, excl = 0; for (const x of a) { const newExcl = Math.max(incl, excl); incl = excl + x; excl = newExcl; } return Math.max(incl, excl);}