# Is it possible to solve it in one pass?

• Is it possible to solve it in one pass?

• This post is deleted!

• 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[k-1] + f(k-2), f(k-1))

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(k-2), f(k-1))
'''
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[i-1] + firstIncluded[i-2], firstIncluded[i-1])
firstExcluded[i] = max(nums[i] + firstExcluded[i-2], firstExcluded[i-1])

return max(firstIncluded[-1], firstExcluded[-1])
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.