213. 打家劫舍 II

213. 打家劫舍 II

题目描述

解题思路
这个和打家劫舍一最大的差别是首位连起来了，思路就是把环形的分成两条单队列，要么偷第一个不偷最后，要么偷最后不偷第一个。

public int rob(int[] nums) {        
	int n = nums.length;        
	if(0 == n)            
		return 0;        
	if(1 == n)            
		return nums[0];        
	return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)), myRob(Arrays.copyOfRange(nums, 1, nums.length)));    
}    
public int myRob(int[] nums) {            
	int n = nums.length;         
	int pre1 = 0,pre2 = 0,max = 0;  //pre1位置上的前一个，pre2前两个
	for (int i = 0; i < n; i++) {            
		max = Math.max(pre2+nums[i], pre1);            
		pre2 = pre1;            
		pre1 = max;        
	}        
	return pre1;
}