Find Maximum Possible Loot from not Adjacent Houses
package org.wesome.dsalgo;
public class MaxPossibleLoot {
public static int findMaxPossibleLoot(int houseArr[]) {
int noOfHouse = houseArr.length;
if (noOfHouse == 0) {
System.out.println("house array is empty");
return 0;
}
if (noOfHouse == 1) {
System.out.println("only 1 house is available, hence its value is the maximum loot possible");
return houseArr[0];
}
if (noOfHouse == 2) {
System.out.println("only 2 house are available, hence maximum of both is the maximum loot possible");
return Math.max(houseArr[0], houseArr[1]);
}
/* base conditions for max loot dp */
int[] maxLootDp = new int[noOfHouse];
maxLootDp[0] = houseArr[0];
maxLootDp[1] = Math.max(houseArr[0], houseArr[1]);
/* since we already know the initial 2 values of maxLootDp array, we will start from 3rd house ie 2nd index */
for (int indx = 2; indx < noOfHouse; indx++) {
maxLootDp[indx] = Math.max(houseArr[indx] + maxLootDp[indx - 2], maxLootDp[indx - 1]);
}
return maxLootDp[noOfHouse - 1];
}
}