instagram

Google Interview Dynamic Programming on Stolen Values

by omt

There are n houses built in a line, each of which contains some value in it. A thief is going to steal the maximal value in these houses, but he cannot steal in two adjacent houses because the owner of a stolen house will tell his two neighbors on the left and right side. What is the maximal stolen value?

Input : { 100, 4, 1, 6, 1, 8, 8, 98 }
Output : 212

Here I am going to implement this algorithm using three ways. 

package com.omt.learn.algo;

public class HousesWithMoneyThif {

	public static void main(String[] args) {
		int a[] = { 100, 4, 1, 6, 1, 8, 8, 98 };//
		// int a[] = { 8, 5, 10, 40, 50, 35 };
		System.out.println(getMaxTotal(a));
		System.out.println(maxValue(a, 0));

	}

	/**
	 * Method ONE
	 */
	public static int getMaxTotal(int a[], int i) {

		if (i >= a.length) {
			return 0;
		}

		int one = a[i] + getMaxTotal(a, i + 2);
		int two = getMaxTotal(a, i + 1);

		return Math.max(one, two);

	}

	/**
	 * Method TWO
	 */
	public static int getMaxTotal(int a[]) {

		int nextElement = a[0];
		int justGotChance = a[1];

		for (int i = 2; i < a.length; i++) {
			int tempBigElement = Math.max(nextElement, justGotChance);
			nextElement += a[i];
			justGotChance = nextElement;
			nextElement = tempBigElement;
		}
		return Math.max(nextElement, justGotChance);
	}

	/**
	 * Method THREE
	 */
	public static int maxValue(int a[], int i) {

		if (i >= a.length) {
			return 0;
		}

		int one = a[i] + maxValue(a, i + 2);
		int two = a[i] + maxValue(a, i + 3);
		int three = maxValue(a, i + 1);

		return Math.max(Math.max(one, two), three);

	}

}
Share