House Robber II
Source
Note: This is an extension of House Robber.
After robbing those houses on that street, the thief has found himself a
new place for his thievery so that he will not get too much attention. This
time, all houses at this place are arranged in a circle. That means the
first house is the neighbor of the
last one. Meanwhile, the security system for these houses remain the
same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of
each house, determine the maximum amount of money you can rob tonight
without alerting the police.
Java
public class Solution {
private int robAlongALine(int[] nums){
int a =0;
int b=0;
for(int i=0; i<nums.length; i++){
if(i%2==0){
a+=nums[i];
a = Math.max(a, b);
}
else{
b+=nums[i];
b = Math.max(a, b);
}
}
return Math.max(a, b);
}
public int rob(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
if (nums.length == 2) return Math.max(nums[0], nums[1]);
int maxWithFirst = robAlongALine(Arrays.copyOfRange(nums, 0, nums.length - 1));
int maxWithoutFirst = robAlongALine(Arrays.copyOfRange(nums, 1, nums.length));
return Math.max(maxWithFirst, maxWithoutFirst);
}
}