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


  • 0

    C++

    class Solution {
    private:
        int rob(const vector<int>& nums, const int& start, const int& end) {
            if(nums.size() <= start)
                return 0;
            if(nums.size() == start + 1)
                return nums[start];
            int res_prev = nums[start];
            int res = max(nums[start], nums[start + 1]);
            for(int i = start + 2; i < end; ++i) {
                int tmp = res;
                res = max(nums[i] + res_prev, res);
                res_prev = tmp;
            }
            return res;
        }
    public:
        int rob(const vector<int>& nums) {
            return max(rob(nums, 0, nums.size() - 1), rob(nums, 1, nums.size()));
        }
    };
    

    Python

    class Solution(object):
        def rob(self, nums):
            return max(self.rob_helper(nums, 0, len(nums) - 1), self.rob_helper(nums, 1, len(nums)))
            
        def rob_helper(self, nums, start, end):
            if(len(nums) <= start):
                return 0
            if(len(nums) == start + 1):
                return nums[start]
            res_prev = nums[start]
            res = max(nums[start], nums[start + 1])
            for i in range(start + 2, end):
                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.