213.House Robber II

Posted on | In

Test case

1
2
3
4
5
6
7
8
9
10
11
12
[]
[1]
[1,2]
[2,1]
[1,3,2]
[1,2,3]
[1,2,3,4,5,6,8]
[8,6,5,4,3,2,1]
[1,2,3,4,5,6,7,8]
[8,7,6,5,4,3,2,1]
[1,0,3,5,6,4,1,4,2,9,5,8]
[1,0,3,5,6,4,1,4,2,9,5,8,6]

Solution 1: accepted 0ms

Time: O(n), Space: O(1)
Based on the solution of House Robber 1, the only difference is that, we cannot rob both of the first and the last house at one time. So we assume two situations, one includes only the first house, the other includes only the last house. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 1) return nums[0];
        int group1 = robRange(nums, 1, len);        
        int group2 = robRange(nums, 0, len-1);
        return Math.max(group1, group2);
    }
    
    private int robRange(int nums[], int start, int end) {
        int doit = 0; // total stash if we do rob the current house
        int dont = 0; // total stash if don't rob the current house
        for(int i = start; i < end; i++) {
            int current = dont + nums[i];
            dont = Math.max(doit, dont);
            doit = current;
        }       
        return Math.max(dont, doit);
    }
}