1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int rob(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int firstMax = 0, secondMax = 0, ans = 0;
for (int i = 0; i < nums.length - 1; i++) {
int currMax = Math.max(firstMax + nums[i], secondMax);
firstMax = secondMax;
secondMax = currMax;
}
ans = secondMax;
firstMax = 0;
secondMax = 0;
for (int i = 1; i < nums.length; i++) {
int currMax = Math.max(firstMax + nums[i], secondMax);
firstMax = secondMax;
secondMax = currMax;
}
ans = Math.max(ans, secondMax);
return ans;
}
}
|
首尾不能挨着抢, 其实就是从0到nums.length - 2范围(两端均inclusive)和1到nums.length - 1(两端均inclusive)看哪个范围抢得大.
时间复杂度: O(n)
空间复杂度: O(1)
