1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int rob(vector<int>& nums) {
const int n = nums.size();
if (n == 1) return nums[0];
if (n == 2) return max(nums[0], nums[1]);
return max(rob(nums, 0, n - 1), rob(nums, 1, n));
}
int rob(vector<int>& nums, int start, int end) {
int pre2 = nums[start], pre1 = max(nums[start], nums[start + 1]), tmp;
for (int i = start + 2; i < end; ++i) {
tmp = max(pre2 + nums[i], pre1);
pre2 = pre1;
pre1 = tmp;
}
return max(pre1, pre2);
}
};
|