My divide-and-conquer 0ms c++ solution


  • 1
    N
    class Solution {
    public:
        int rob(vector<int>& nums) {
            return myRob(nums,0,nums.size()-1);
        }
        
        int myRob(vector<int>& nums,int begin,int end){
            int size = end-begin+1;
            if(size<=0) return 0;
            if(size==1) return nums[begin];
            if(size==2) return max(nums[begin],nums[end]);
            
            int half = size/2;
            //  nums = [... a = nums[begin+half-1] b = nums[begin+half] ...]
            int c1 = myRob(nums,begin,begin+half-1);    // includes a
            int c2 = myRob(nums,begin,begin+half-2);    // does not include a
            int c3 = myRob(nums,begin+half,end);        // includes b
            int c4 = myRob(nums,begin+half+1,end);      // does not include b
            
            return max(c1+c4,max(c2+c3,c2+c4));
        }
    };

Log in to reply
 

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