My 4-lines O(n) Python solution


  • 0

    The time complexity is O(n^2)!
    But I really like the style of python.

    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def rob(self, nums, circle=True):
            if circle: return max([0]+[nums[i]+self.rob((nums[i:]+nums[0:i])[2:-1], False) for i in range(len(nums))])
            pre, now = 0, 0
            for i in nums: pre, now = now, max(pre + i, now)
            return now
    

    UPDATE O(n) solution, also 4 lines:

    class Solution:
        # @param {integer[]} nums
        # @return {integer}
        def rob(self, nums, circle=True):
            # self.rob(nums[0:1], False) to handle nums.length == 1
            if circle: return max(self.rob(nums[1:], False), self.rob(nums[:-1], False), self.rob(nums[0:1], False))
            pre, now = 0, 0
            for i in nums: pre, now = now, max(pre + i, now)
            return now

  • 0
    Y

    it's so hard to understand...can you explain to me?


Log in to reply
 

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