# House robber 2

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are **arranged in a circle.** That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given an integer array `nums`

representing the amount of money of each house, return *the maximum amount of money you can rob tonight *** without alerting the police**.

Compared to House robber problem, only one condition is added that is first and last elements are adjacent.

This one extra condition is making to calculate 2 sets of values:

- One set to consider only elements of indices 0 to n-2 (not taking last element)
- Another set to consider only elements of indices 1 to n-1 (not taking first element)

In both calculations, double time addition of elements of indices from 1 to n-2 are involved.

Please comment if any possibility there to optimize.

Solution 1:

`int rob(int* nums, int ns){`

int ii, s0, s1, s, s2,mx;

/* last and first are connected */

/* so these should not be added */

if (!ns) return 0;

s0 = nums[0];

if (ns==1) return nums[0];

/* first element and last element should not be included together,

compute 2 sets : 2 to n and 1 to n-1 ,

choose the best of out

One issue here is, double time additions of elements between 2 and n indices*/

s0 = 0;

mx = s1 = nums[1];

for (ii=2; ii<ns; ii++){

if (s1 < (s0 + nums[ii])) {

s = s0 + nums[ii];

} else {

s = s1;}

if (mx < s)

mx =s;

s0 = s1; s1 =s;

}

s1 = nums[0]; s0 = 0;

if (mx < s1)

mx =s1;

for (ii=1; ii<ns-1; ii++){

if (s1 < s0+nums[ii]) s= s0+nums[ii];

else s = s1;

if (mx < s) mx = s;

s0 = s1; s1= s;

}

return mx;

}

Solution 2:

`/*`

derive 2 values : 0 to n-2 indices, 1 to n-1 indices

calculate these 2 values in a single for loop.

This is just to reduce one loop, but no optimization

*/

int rob(int* nums, int ns){

int ii, mx=0, v0s0, v0s1, v1s0,v1s1,s;

/*v0s0 , v0s1 for 0 to n-2

v1s0, v1s1 for 1 to n-1 */

v0s0 = v1s0 = 0;

if (ns == 1)

return nums[0];

v0s1 = nums[0];

v1s1 = nums[1];

if (ns == 2)

return (v0s1 > v1s1 ? v0s1 : v1s1);

for (ii=1; ii<ns-1; ii++){

if (v0s1 > v0s0+nums[ii]) s = v0s1;

else s = v0s0 + nums[ii];

v0s0 = v0s1; v0s1 =s;

if (mx < s) mx = s;

if (v1s1 > v1s0 + nums[ii+1]) s = v1s1;

else s =v1s0 + nums[ii+1];

v1s0 =v1s1; v1s1 = s;

if (mx < s) mx =s;

}

return mx;

}