LeetCode 213. House Robber II
The trick is to find the max value between robbing 0 to n-2 and 1 to n-1, so that we avoid the rounding issue.
public class Solution {
public int Rob(int[] nums) {
int len = nums.Length;
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[] h = new int[nums.Length];
h[0] = nums[0];
h[1] = nums[1];
for(int i = 2; i < nums.Length-1; i++){
int max = int.MinValue;
for(int j = 0; j < i - 1; j++){
max = Math.Max(nums[i] + h[j], max);
}
h[i] = max;
}
int h1 = Math.Max(h[len-2], h[len-3]);
h[1] = nums[1];
h[2] = nums[2];
for(int i = 3; i < nums.Length; i++){
int max = int.MinValue;
for(int j = 1; j < i - 1; j++){
max = Math.Max(nums[i] + h[j], max);
}
h[i] = max;
}
int h2 = Math.Max(h[len-1], h[len-2]);
return Math.Max(h1, h2);
}
}