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

• 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);
}
};

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