Max Look

MaxLoot.java

/**
 * Deepak Singhvi
 */
public class MaxLoot {
  public static int maxLoot(int input[], int inputSize)
  {
    if (inputSize == 0)
      return 0;
    if (inputSize == 1)
      return input[0];
    if (inputSize == 2)
      return Math.max(input[0], input[1]);

    // maxLoot[i] is the temporary store value at any point of time of calculation.
    // maxLoot[n-1] i.e. the last element would have maximum loot value.
    int[] maxLoot = new int[inputSize];

    maxLoot[0] = input[0];
    maxLoot[1] = Math.max(input[0], input[1]);

    for (int i = 2; i<inputSize; i++)
      maxLoot[i] = Math.max(input[i]+maxLoot[i-2], maxLoot[i-1]);

    return maxLoot[inputSize-1]; // maximum loot value.
  }
  public static void main (String[] args) {
    int input[] = {5, 5, 10, 100, 10, 5};
    System.out.println("Maximum loot value : " + maxLoot(input, input.length));
    input = new int[]{1,2,3};
    System.out.println("Maximum loot value : " + maxLoot(input, input.length));

  }
}