LeetCode 213. House Robber II

问题描述

地址

问题分析

该题是 LeetCode 198. House Robber 进阶题，基本方法还是一样， 该题是把数组看成一个环，数组的首部和尾部同样也有邻居关系，不能同时选择。方法： 既然首部和尾部不能同时选择，那么我们先求 nums[0 ~ end - 1]的最大抢劫和， 再求 nums[1 ~ end] 的最大抢劫和，两者求其大即为所求。

代码实现

class Solution { public int rob(int[] nums) { if (nums == null || nums.length == 0) { return 0; } if (nums.length == 1) { return nums[0]; } if (nums.length == 2) { return Math.max(nums[0], nums[1]); } //经过上两次判断，保证了此刻nums数组长度一定大于等于3，去头或者去尾后一定大于等于2 return Math.max(maxRob(nums, 0, nums.length - 2), maxRob(nums, 1, nums.length - 1)); } //求nums[begin ~ end]中的最大抢劫和 public int maxRob(int[] nums, int begin, int end) { int pre = nums[begin]; int cur = Math.max(nums[begin], nums[begin + 1]); for (int j = begin + 2; j <= end; ++j) { int temp = cur; cur = Math.max(pre + nums[j], cur); pre = temp; } return cur; } }