Is it possible to solve it in one pass?

Python code with embedded comments
class Solution: # @param {integer[]} nums # @return {integer} def rob(self, nums): # corner cases if len(nums) < 3: return 0 if len(nums) == 0 else max(nums) ''' use two lists: one to rob the first house, the other not to rob the first house DP formula (rob first house, which means we can't rob the last house): f(0) = f(1) = f(2) = nums[0] f(k) = max(nums[k1] + f(k2), f(k1)) DP formula (don't rob first house, which means we can rob the last house): f(0) = 0, f(1) = nums[1], f(2) = max(nums[1], nums[2]) f(k) = max(nums[k] + f(k2), f(k1)) ''' firstIncluded, firstExcluded = [0] * len(nums), [0] * len(nums) firstIncluded[0] = firstIncluded[1] = firstIncluded[2] = nums[0] firstExcluded[0], firstExcluded[1], firstExcluded[2] = 0, nums[1], max(nums[1], nums[2]) for i in xrange(3, len(nums)): firstIncluded[i] = max(nums[i1] + firstIncluded[i2], firstIncluded[i1]) firstExcluded[i] = max(nums[i] + firstExcluded[i2], firstExcluded[i1]) return max(firstIncluded[1], firstExcluded[1])