Walk down the street keeping the best total so far. At each house there are only two options: skip it and keep the best total up to the house before, or rob it and add its value to the best total two houses back, because its neighbour must be skipped. Take the larger.
- Average time
- O(n)
- Space
- O(n)