Google Interview Dynamic Programming on Stolen Values

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);

}

}
```