C++ 0ms concise solution, O(n) time and O(1) space.


  • 0
    G
    class Solution {
    public:
        int rob(vector<int>& nums) {
            if (nums.size() == 0) return 0;
            if (nums.size() == 1) return nums[0];
            if (nums.size() == 2) return max(nums[0], nums[1]);
            int prev1 = nums[1], prev2 = nums[0], prev1_no_rob = nums[0], cur;
            for (int i = 2; i < nums.size(); i++)
            {
                cur = max(prev1_no_rob + nums[i], max(prev1, prev2 + nums[i]));
                prev1_no_rob = max(prev2, prev1);
                prev2 = prev1;
                prev1 = cur;
            }
            return cur;
        }
    };
    

Log in to reply
 

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