Python solution, O(n) time, constant space


  • 0
    0

    Basically DP. Store the max attainable by robbing up to each of the previous two houses (prevprev and prev); then you can either:

    • don't rob the current house, in which case you can get the value up to the previous house, or
    • rob the current house, in which case the max is its value plus the max for two houses back.
    def rob(self, nums):
        prevprev = 0
        prev = 0
        for i in xrange(len(nums)):
            tmp = prev
            prev = max(nums[i]+prevprev, prev)
            prevprev = tmp
        return prev
    

Log in to reply
 

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