package dynamic;

/**题目:抢劫环形房子
 * y: a[]{8,1,2,9,6}
 * @Author Gavin
 * @date 2022年01月09日 10:36
 */
public class solution_5 {
 /**
 * 解题思路:本题是一个动态规划题目,和solution_4解题思路是一样的
 * 只是本地是一个环形的房子,就是首尾是相邻的两个房子,所以不能同时抢
 * 首尾两个房子,所以思路就是去掉首或者尾按照连排的方式计算,然后比较求
 * 最大值就行
 */
 //Time:O(n) Space:O(1)
 public int solution(int[] nums){
 if(nums==null||nums.length==0)return 0;
 if(nums.length==1)return nums[0];
 int n=nums.length;
 return Math.max(help(nums,0,n-2),help(nums,1,n-1));
 }


 public int help(int[] nums,int start,int end){
 int prev1=0,prev2=0;
 for (int i=start;i<=end;++i){
 int cur=Math.max(prev1,prev2+nums[i]);
 prev2=prev1;
 prev1=cur;
 }
 return prev1;
 }
}