1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 | public 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]);
}
int length = nums.length;
int robFirst[] = new int[length-1];
int robLast[] = new int[length-1];
robFirst[0] = nums[0];
robFirst[1] = robFirst[0] > nums[1]?robFirst[0]:nums[1];
robLast[0] = nums[1];
robLast[1] = robLast[0] > nums[2]?robLast[0]:nums[2];
for (int i = 2; i < length-1; i++){
robFirst[i] = Math.max(nums[i]+robFirst[i-2], robFirst[i-1]);
robLast[i] = Math.max(nums[i+1]+robLast[i-2], robLast[i-1]);
}
return Math.max(robFirst[length-2], robLast[length-2]);
}
}
|
No comments:
Post a Comment