Is it possible to solve it in one pass?


  • 0
    N

    Is it possible to solve it in one pass?


  • -1
    C
    This post is deleted!

  • -1
    D

    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])
    

Log in to reply
 

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