C++, Python Solutions. O(n) time, O(1) space.


  • 0

    C++

    int rob(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;
        if(nums.size() == 1)
            return nums[0];
        int res_prev = nums[0];
        int res = max(nums[0], nums[1]);
        for(int i = 2; i < nums.size(); ++i) {
            int tmp = res;
            res = max(nums[i] + res_prev, res);
            res_prev = tmp;
        }
        return res;
    }
    

    Python

    def rob(self, nums):
        if(len(nums) == 0):
            return 0
        if(len(nums) == 1):
            return nums[0]
        res_prev = nums[0]
        res = max(nums[0], nums[1])
        for i in range(2, len(nums)):
            res, res_prev = max(nums[i] + res_prev, res), res
        return res
    

Log in to reply
 

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