House Robber

Each house on a street holds some money, and robbing two adjacent houses trips the alarm. Return the most money you can rob.

A way to picture it

A polite raccoon raids bins down a street, but raiding two neighbours in a row wakes the dogs. At each bin: raid it and add the best haul from two bins back, or skip it and keep the best haul so far.

How to approach it

best(i) = max(best(i − 1), nums[i] + best(i − 2)). Only the last two values are ever needed.

Example

Input: {"nums":[1,2,3,1]}. Output: 4.

Complexity: O(n) time and O(1) space. One pass with two running values.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.