/ Data Structure and Algorithms  

Leetcode 213. House Robber II

Question



Gavin an array, each element represents the deposit of the store. A thief went to steal the store at night. Need to determine how much money can be stolen at most. The neighboring shops cannot be stolen otherwise the alarm will sound. The stores are distributed in a circle, so the first and last ones are also counted as adjacent stores.

Similar Questions

Solution

Because first and last one can’t be stolen together, so we have 2 situations:

  1. Stealing the first one. We need to find the maximum money of stealing in the first n - 1 households. That is, not considering the maximum gain of the last one.
  2. Do not steal the first one. We need to find the maximum money from the second to the last one. That is, do not consider the maximum gain of the first one.

Then we only need to return to the larger of the above.

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
28
29
30
31
32
33
34
35
36
37
38
public int rob(int[] nums) {
    // special case
    if (nums.length == 0) {
        return 0;
    }

    if (nums.length == 1) {
        return nums[0];
    }

    // 2 conditions
    // if rob 1st home, then just consider max of (1st, last-1)
    // if not rob 1st home, them consider (2rd, last)
    int max1 = robHelper(nums, 0, nums.length - 1);
    int max2 = robHelper(nums, 1, nums.length);

    return Math.max(max1, max2);
}

private int robHelper(int[] nums, int start, int end) {
    // max if rob previous one
    int ifRobPrevious = 0;
    // max if not rob previous one
    int ifNotRobPrevious = 0;

    for (int i = start; i < end; i++) {
        // if rob current one, then must not rob previous one
        int ifRobCurrent = ifNotRobPrevious + nums[i];

        // if not rob current one, then take max of ifRobPrevious and ifNotRobPrevious
        int ifNotRobCurrent = Math.max(ifRobPrevious, ifNotRobPrevious);

        ifNotRobPrevious = ifNotRobCurrent;
        ifRobPrevious = ifRobCurrent;
    }

    return Math.max(ifRobPrevious, ifNotRobPrevious);
}