O(n) time O(1) space DP C++ solution


  • 0

    It is possible to do this with only one loop, but I think two loops make code clearer. First do the calculation from 0 to n-1, and then from 1 to n, just like House Robbery I.

    int rob(vector<int>& nums) {
        if( nums.empty()) return 0;
        if( nums.size() == 1 ) return nums[0];
        int ans = 0, a,b,c,d,p,q;
        for( int i=0; i<nums.size()-1; i++ ) {
            p = i < 2 ? 0 : b;
            q = i < 3 ? 0 : a;
            d = max(p, q) + nums[i];
            ans = max( ans, d);
            a = b; b = c; c = d;
        }
    
        for( int i=1; i<nums.size(); i++ ) {
            p = i < 3 ? 0 : b;
            q = i < 4 ? 0 : a;
            d = max(p, q) + nums[i];
            ans = max( ans, d);
            a = b; b = c; c = d;
        }
        return ans;
    }

Log in to reply
 

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