My straightforward C++ solution using three arrays ...


  • 0
    B
        // A[i]: 0 -- i circle
        // B[i]: 1 -- i non-circle
        // C[i]: 0 -- i non-circle
        // A[i] = max(C[i-1], nums[i-1]+B[i-2])
        int rob(vector<int>& nums) {
            int nums_size = nums.size();
            if(nums_size == 0)
                return 0;
            else if(nums_size == 1)
                return nums[0];
            vector<int> A(nums_size+1, 0), B(nums_size+1, 0), C(nums_size+1, 0);
            A[1] = nums[0];
            C[1] = nums[0];
            for(int i = 2; i <= nums_size; ++i) {
                B[i] = max(B[i-1], nums[i-1]+B[i-2]);
                C[i] = max(C[i-1], nums[i-1]+C[i-2]);
                A[i] = max(C[i-1], nums[i-1]+B[i-2]);
            }
            return A[nums_size];
        }
    

Log in to reply
 

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