[LeetCode]House Robber II

和House Robber一样的，这里唯一的区别就是取了第一个不能取最后一个，取了最后一个不能取第一个。那么我们只需要根据这个分取第一个和不取第一个两种情况就可以了，算法和House Robber是一样的，我们算一次[0, len - 2]的最大值和[1, len - 1]的最大值然后取最大的就可以了。O(n)时间，常数空间，代码如下：

	class Solution {
	public:
	int rob(vector<int>& nums) {
	int len = nums.size();
	if(len == 1)return nums[0];
	return max(rob(nums, 0, len - 2), rob(nums, 1, len - 1));
	}
	private:
	int rob(vector<int>& nums, int lo, int hi)
	{
	if(lo > hi)return 0;
	int localMax1 = 0, localMax2 = 0;
	for(int i = lo; i <= hi; ++i)
	{
	int currMax = max(localMax1 + nums[i], localMax2);
	localMax1 = localMax2;
	localMax2 = currMax;
	}
	return max(localMax1, localMax2);
	}
	};

view raw House Robber II.cpp hosted with ❤ by GitHub