-
Notifications
You must be signed in to change notification settings - Fork 0
/
GoogleInterviewCodingChallenge7.java
49 lines (38 loc) · 1.56 KB
/
GoogleInterviewCodingChallenge7.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
public class GoogleInterviewCodingChallenge7 {
public static void main(String[] args) {
/*
You are a professional robber planning to rob houses along a street. Each hose has a certain amount of
money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security
system connected and it will automatically contact the police if two adjacent houses were broken into on the
same night.
Given a list of non-negative integers representing the amount of money of each house,
determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output : 4
Explanation: Rob hose 1 ( money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output : 12
Explanation: Rob hose 1 ( money = 2), rob house 3 (money = 9) and rob house 5 ( money= 1).
Total amount you can rob = 2 + 9 + 1 = 12.
*/
int[] nums = {2,7,9,3,1};
System.out.println(rob(nums));
}
public static int rob(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(dp[i-1],dp[i-2]+nums[i]);
}
return dp[dp.length-1];
}
}