data-structures/src/com/leetcode/problems/medium/HouseRobberCircular.java at master · 1shika/data-structures · GitHub

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package com.leetcode.problems.medium;

import java.util.Arrays;

/**
 * @author neeraj on 05/09/19
 * Copyright (c) 2019, data-structures.
 * All rights reserved.
 */
public class HouseRobberCircular {

    public static void main(String[] args) {
        System.out.println(rob(new int[]{1,2,3,1}));
        System.out.println(rob(new int[]{2,7,9,3,1}));
    }

    public static int rob(int[] nums) {
        if(nums.length == 0)
            return 0;
        if(nums.length == 1)
            return nums[0];
        if(nums.length == 2)
            return Math.max(nums[0], nums[1]);
        if(nums.length == 3)
            return Math.max(Math.max(nums[0], nums[1]), nums[2]);

        // Now the tricky part,
        // if i choose 1st House to Rob, i can't choose HouseNo(1) and HouseNo(totalHouses);
        // Since the houses are in circular fashion
        // So 2 condition
        return Math.max(
                nums[0] + robBasic(Arrays.copyOfRange(nums, 2, nums.length - 1)),
                robBasic(Arrays.copyOfRange(nums, 1, nums.length))
        );
    }

    public static int robBasic(int[] nums) {
        if(nums.length == 0) {
            return 0;
        }
        if(nums.length == 1) {
            return nums[0];
        }

        int [] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for(int i=2;i<nums.length;i++) {
            dp[i] = Math.max((nums[i] + dp[i-2]), dp[i - 1]);
        }

        return dp[nums.length - 1];
    }

}