Maximize the robbery

A robber enters a colony of houses numbered from 1 to n.  Every house has a number printed on the top of it. That number is the amount of money inside that house. However, there is one constraint. If the robber cannot robs from money from consecutive houses. How can the robber maximize his robbery?

Solution:

If Robber robs from i-th house, he can't rob house no i-1 and house no i+1.

Dynamic Programming logic:

dp[i] = Math.max(dp[i - 2] + amPerHouse[i], dp[i - 1]);

Implementation in Java:

import java.util.Scanner;

public class MaximiseRobbery {

     public static void main(String[] args) {

           Scanner scan = newScanner(System.in);

           int houses = scan.nextInt();

           int[] amPerHouse = newint[houses];

           for (inti = 0; i < houses; i++) {

                amPerHouse[i] = scan.nextInt();

           }

           int maximumRobbery = maximizeRobbery(amPerHouse, houses);

           System.out.println(maximumRobbery);

           scan.close();

     }

    

     /**

      * Method to maximise the robbery

      * @param amPerHouse

      */

     private static int maximizeRobbery(int[] amPerHouse,inthouses) {

        if(houses == 1) {

              return amPerHouse[0];

        } elseif (houses == 2) {

              return Math.max(amPerHouse[0], amPerHouse[1]);

        }

        int[] dp = newint[amPerHouse.length];

        dp[0] = amPerHouse[0];

        dp[1] = amPerHouse[1];

        for(int i = 2; i < houses; i++) {

           dp[i] = Math.max(dp[i - 2] + amPerHouse[i], dp[i - 1]);

        }

        return dp[houses - 1];

     }

}

Reference:

http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/