forked from prateekshyap/DSA
-
Notifications
You must be signed in to change notification settings - Fork 0
/
HouseRobber2.java
92 lines (86 loc) · 2.85 KB
/
HouseRobber2.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
86
87
88
89
90
91
92
/*https://leetcode.com/problems/house-robber-ii/*/
class Solution {
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
if (nums.length == 2) return Math.max(nums[0],nums[1]);
int[] dp = new int[nums.length-1];
int[] maxTillPoint = new int[nums.length-1];
dp[0] = maxTillPoint[0] = nums[0];
dp[1] = nums[1];
maxTillPoint[1] = Math.max(maxTillPoint[0],dp[1]);
for (int i = 2; i < nums.length-1; ++i)
{
dp[i] = maxTillPoint[i-2]+nums[i];
maxTillPoint[i] = Math.max(maxTillPoint[i-1],dp[i]);
}
int result = maxTillPoint[nums.length-2];
dp[0] = maxTillPoint[0] = nums[1];
dp[1] = nums[2];
maxTillPoint[1] = Math.max(maxTillPoint[0],dp[1]);
for (int i = 3; i < nums.length; ++i)
{
dp[i-1] = maxTillPoint[i-3]+nums[i];
maxTillPoint[i-1] = Math.max(maxTillPoint[i-2],dp[i-1]);
}
result = Math.max(result,maxTillPoint[nums.length-2]);
return result;
}
}
class Solution {
Integer[] maxRob;
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
if (nums.length == 2) return Math.max(nums[0],nums[1]);
maxRob = new Integer[nums.length+2];
int max = 0;
solve(nums, 1, false);
max = maxRob[1];
maxRob = new Integer[nums.length+2];
solve(nums, 0, true);
max = Math.max(max,maxRob[0]);
return max;
}
public int solve(int[] nums, int index, boolean takeFirst)
{
if (!takeFirst && index >= nums.length)
{
maxRob[index] = 0;
return 0;
}
if (takeFirst && index >= nums.length-1)
{
maxRob[index] = 0;
return 0;
}
if (maxRob[index] != null) return maxRob[index];
maxRob[index] = Math.max(solve(nums,index+1,takeFirst),solve(nums,index+2,takeFirst)+nums[index]);
return maxRob[index];
}
}
class Solution {
public int rob(int[] nums) {
int i, n = nums.length, last = -1, secondLast = -1, curr = -1, max = 0;
if (n == 1) return nums[0];
if (n == 2) return Math.max(nums[0],nums[1]);
secondLast = nums[0];
last = Math.max(nums[0],nums[1]);
max = Math.max(last,secondLast);
for (i = 2; i < n-1; ++i)
{
curr = Math.max(last,secondLast+nums[i]);
secondLast = last;
last = curr;
}
max = Math.max(max,curr);
secondLast = nums[1];
last = Math.max(nums[1],nums[2]);
max = Math.max(max,Math.max(last,secondLast));
for (i = 3; i < n; ++i)
{
curr = Math.max(last,secondLast+nums[i]);
secondLast = last;
last = curr;
}
return Math.max(curr,max);
}
}