Simple c++ solution, time 0 ms, space O(1)


  • 0
    S
    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 n = nums.size();
            int ppBest = nums[0], pBest = max(nums[0], nums[1]), best = pBest;
            for(int i = 2; i < n-1; i++){
                best = max(ppBest+nums[i], pBest);
                ppBest = pBest;
                pBest = best;
            }
            int tmp = best;
            ppBest = nums[n-1], pBest = max(nums[n-1], nums[n-2]), best = pBest;
            for(int i = n-3; i > 0; i--){
                best = max(ppBest+nums[i], pBest);
                ppBest = pBest;
                pBest = best;
            }
            best = max(best, tmp);
            return best;
        }
    };

Log in to reply
 

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