Maximum sum such that no two elements are adjacent (House Robber)

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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);
}