C++ O(n) time, O(1) space, easy solution


  • 0
    J
    class Solution {
    public:
        int rob(vector<int>& nums) {
            int n = nums.size();
            if(n < 1)
            {
                return 0;
            }
            
            if(n == 1)
            {
                return nums[0];
            }
            
            int x1 = 0;
            int x2 = 0;
            int y1 = 0;
            int y2 = 0;
            int ret1 = 0;
            int ret2 = 0;
    
            for(int i=0;i<n;i++)
            {
                if(i < n-1)
                {
                    ret1 = (x1 + nums[i] > y1 ? x1 + nums[i] : y1);
                    x1 = y1;
                    y1 = ret1;
                }
                
                if(i > 0)
                {
                    ret2 = (x2 + nums[i] > y2 ? x2 + nums[i] : y2);
                    x2 = y2;
                    y2 = ret2;
                }
            }
            
            return ret1 > ret2 ? ret1 : ret2;
        }
    };

Log in to reply
 

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