0 ms C++ Solution O(n) time O(1) space


  • -7
    D
    class Solution {
    public:
        inline int max(int a, int b){
            return (a>b)?a:b;
        }
        inline int rob(vector<int>& nums) {
            if (nums.size() == 0) return 0;
            else if (nums.size() == 1) return nums[0];
            else if (nums.size() == 2) return max(nums[0], nums[1]);
            else if (nums.size() == 3) return max(nums[0], max(nums[1], nums[2]));
            else if (nums.size() == 4) return max(nums[0]+nums[2], nums[1]+nums[3]);
            else if (nums.size() == 5) return max(max(nums[0]+nums[2], nums[0]+nums[3]), max(nums[1]+nums[3], nums[1]+nums[4]));
            else if (nums.size() == 6) return max(max(max(nums[0]+nums[2]+nums[4], nums[0]+nums[3]), max(nums[0]+nums[4], nums[1]+nums[3])),
                max(max(nums[1]+nums[3]+nums[5], nums[1]+nums[4]), nums[2]+nums[5]));
            int p[3], q[3], r[3], i;
            p[2] = nums[0] + nums[2];
            p[0] = nums[0] + nums[3];
            p[1] = nums[0] + nums[2] + nums[4];
            q[0] = nums[1] + nums[3];
            q[1] = nums[1] + nums[4];
            q[2] = nums[1] + nums[3] + nums[5];
            r[0] = nums[2];
            r[1] = nums[2] + nums[4];
            r[2] = nums[2] + nums[5];
            i = 6;
            p[2] = max(p[0] + nums[5], p[2] + nums[5]);
            while (i < nums.size() - 1){
                p[i%3] = max(p[(i+1) % 3] + nums[i], p[i % 3] + nums[i]);
                q[i%3] = max(q[(i+1) % 3] + nums[i], q[i % 3] + nums[i]);
                r[i%3] = max(r[(i+1) % 3] + nums[i], r[i % 3] + nums[i]); 
                i+=1;
            }
            q[i%3] = max(q[(i+1) % 3] + nums[i], q[i % 3] + nums[i]);
            r[i%3] = max(r[(i+1) % 3] + nums[i], r[i % 3] + nums[i]);
            return max( max( max(p[0], max(p[1], p[2])), max(q[0], max(q[1], q[2])) ), max(r[0], max(r[1], r[2])) );
        }
    };

Log in to reply
 

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