Simple C++ Solution in O(n) time and O(1) space using DP


  • 0
    B

    This can be solved using dynamic programming with little modification in House Robber I problem.
    Being a circle just introduces one extra constraint that the first element and last element can't be chosen simultaneously.

    Hence, we divide our problem in two parts:

    1. Array from index 0 to n-2.
    2. Array from index 1 to n-1.
    class Solution {
    public:
        /* This function is really similar to the House Robber 1, we have
     just introduced the indices whereas previously it was automatically 
    starting with 0 and ending with n-1. */
        int robbery(vector<int>& nums,int i,int j)
        {
            if(i == j)
                return nums[i];
            else
            {
                int a = nums[i];
                int b = max(a,nums[i+1]);
                for(int k=i+2;k<=j;k++)
                {
                    int temp = b;
                    b = max(b,a+nums[k]);
                    a = temp;
                }
                return max(a,b);
            }
        }
    
        int rob(vector<int>& nums) {
            int l = nums.size(); 
            if(l == 0)
                return 0;
            if(l == 1)
                return nums[0];
            int a = robbery(nums,1,nums.size()-1);
            int b = robbery(nums,0,nums.size()-2);
            return max(a,b);
        }
    };
    

Log in to reply
 

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