Given that you are a professional robber who is planning to rob houses along a street. Constraint given is that each house has a certain amount of money stashed, and adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
you are given a list of non-negative integers representing the amount of money for each house, you have to determine the maximum amount of money you can rob tonight without alerting the police.
We will be using dynamic programming to solve this problem :
public class MaximizeHouseRobberyAmount {
public static void main(String[] args) {
int[] arr = new int[] {2, 7, 9, 3, 1};
System.out.println(CalculateSum(arr));
}
private static int max(int a, int b) {
return a>b?a:b;
}
private static int max(int a, int b, int c) {
if (c > max(a,b))
return c;
else
return max(a,b);
}
private static int CalculateSum(int[] arr) {
int[] sum = new int[arr.length];
if(arr.length <1)
return 0;
sum[0] = arr[0];
sum[1] = arr[1];
sum[2] = max(arr[2]+arr[0],arr[1]);
for(int i=3;i<arr.length;i++)
sum[i] = max(
arr[i-1],
sum[i-2]+arr[i],
sum[i-3]+arr[i]
);
return sum[arr.length-1];
}
}
Output :
12
