Easy to understand python solution


  • 0
    Y
    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def rob_help(self, nums):
                n = len(nums)
                if n < 2:
                    return 0 if not n else nums[0]
    
                prev = 0
                curr = nums[0]
                for i in range(1, n):
                    tmp = max(prev + nums[i], curr)
                    prev, curr = curr, tmp
    
                return curr
    
        def rob(self, nums):
            n = len(nums)
            if n < 2:
                return 0 if not n else nums[0]
    
            nums = [(c, 0) for c in nums]
            nums[0] = (nums[0][0], 1)
            nums[-1] = (nums[-1][0], 1)
    
            prev = (0, False)
            curr = nums[0]
            for i in range(1, n):
                tmp = curr
                if prev[0] + nums[i][0] > curr[0]:
                    curr = (prev[0] + nums[i][0], prev[1] + nums[i][1])
                prev = tmp
    
            # if both the first and the last house are robbed, try robbing only one of them and return the larger one   
            if curr[1] == 2:
                return max(self.rob_help([c[0] for c in nums[1:]]), self.rob_help([c[0] for c in nums[:-1]]))
            else:
                return curr[0]

Log in to reply
 

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