Python O(N) solution beating 100%


  • 0
    U
    class Solution(object):
        def rob(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(nums) == 0:
                return 0
            elif len(nums) <= 2:
                return max(nums)
            else:
                return max(self.rob_helper(nums[:], 0, len(nums) - 2), self.rob_helper(nums[:], 1, len(nums) - 1))
    
        def rob_helper(self, nums, low, high):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums:
                return 0
                
            for index in range(low, high + 1):
                nums[index] = max(nums[index] + (nums[index - 2] if index - 2 >= low else 0), nums[index - 1] if index - 1 >= low else 0)
                
            return nums[high]
    

Log in to reply
 

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