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.