-
Notifications
You must be signed in to change notification settings - Fork 1
/
HouseRobberII.java
85 lines (68 loc) · 2.4 KB
/
HouseRobberII.java
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package com.leetcode;
import java.util.Arrays;
public class HouseRobberII {
//https://leetcode.com/problems/house-robber-ii/
/**
Example 1:
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
**/
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n == 0) return 0;
if(n == 1) return nums[0];
if(n == 2) return Math.max(nums[0],nums[1]);
int[] memo = new int[n];
memo[0] = nums[0];
memo[1] = Math.max(nums[0],nums[1]);
//cant rob 0 and 2 together
memo[2] = Math.max(Math.max(memo[0] , nums[2]), memo[1]);
//check [0 to n-2 ] and [1 to n-1]
int [] nums1 = Arrays.copyOfRange(nums,0,n-1);
int [] nums2 = Arrays.copyOfRange(nums,1,n);
return Math.max(robInLine(nums1),robInLine(nums2));
}
public int robInLine(int[] nums) {
int n = nums.length;
if(n == 0) return 0;
if(n == 1) return nums[0];
if(n == 2) return Math.max(nums[0],nums[1]);
int[] memo = new int[n];
memo[0] = nums[0];
memo[1] = Math.max(nums[0],nums[1]);
memo[2] = Math.max(memo[0] + nums[2], memo[1]);
for(int i = 3 ; i < nums.length ; i++){
memo[i] = Math.max(memo[i-2] + nums[i] , memo[i-1]);
}
return memo[n-1];
}
}
}
// Alternate - above is better for concept and works for House Robber 1
/*
class Solution{
public int rob(int[] nums) {
if(nums== null || nums.length == 0){
return 0;
}
if (nums.length == 1) return nums[0];
return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
}
private int rob(int[] num, int lo, int hi) {
int include = 0, exclude = 0;
for (int j = lo; j <= hi; j++) {
int i = include, e = exclude;
include = e + num[j];
exclude = Math.max(e, i);
}
return Math.max(include, exclude);
}
}
*/