My Python Solution


  • 5
    D
    class Solution(object):
        def rob(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            n = len(nums)
            if n == 0: return 0
            if n < 4: return max(nums)
    
            first, second = 0, 0
            for i in nums[:-1]: first, second = second, max(first + i, second)
            result = second
    
            first, second = 0, 0
            for i in nums[1:]: first, second = second, max(first + i, second)
            return max(result, second)

  • 0

    Same idea but little bit cleaner

    class Solution(object):
        def rob(self, nums):
            def _rob(nums):
                a, b = 0, 0
                for i in xrange(len(nums)):
                    a, b = b, max(a + nums[i], b)
                return b
            a, b = _rob(nums[:-1]), _rob(nums[1:])
            return max(a, b) if len(nums) is not 1 else nums[0]

  • 1
    D

    Another possibility:

    def rob(self, nums):
            if len(nums) == 1: return nums[0]
            ppa, pa, ppb, pb = 0, 0, 0, 0
            for i in range(len(nums)-1):
                ppa, pa = pa, max(pa, ppa + nums[i])
                ppb, pb = pb, max(pb, ppb + nums[i+1])
            return max(pa, pb)
    

Log in to reply
 

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