Sharing my 0ms C++ solution with O(N) dynamic programming


  • 2
    T
    class Solution {
    public:
        int rob(vector<int>& nums) {          
            int n = nums.size();
            if(n==0)
                return 0;
            else if(n==1)
                return nums[0];
            else if(n==2)
                return max(nums[0], nums[1]);
                
            vector<int> DP(n);
            DP[0] = nums[0];
            DP[1] = max(DP[0], nums[1]);
            
            for(int i=2; i<n; i++)
                DP[i] = max(DP[i-1], DP[i-2]+nums[i]);
                
            return DP[n-1];
        }
    };

  • 1
    M
    **c++ 0ms, O(1)space, damn easy solution **   
    
     class Solution {
        public:
            int rob(vector<int>& nums)
            {
                int n=nums.size();
                if(n==0) 
                return 0;
                if(n==1)  
                return nums[0];
                if(n==2)
                return  max(nums[0],nums[1]);
        
                int a=nums[0];
                int b=max(nums[0],nums[1]);
                int c;
                for(int i=2;i<n;i++)
                {
                    c=max(a+nums[i],b);
                    a=b;b=c;
                }
        
                return c;
            }
        };

Log in to reply
 

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