There are n houses build in a line, each of which contains some value in it. A thief is going to steal the maximal value of these houses, but he can’t steal in two adjacent houses because the owner of the stolen
houses will tell his two neighbours left and right side. What is the maximum stolen value?
Sample Input:
val[] = {6, 7, 1, 3, 8, 2, 5}
Sample Output:
20
Solution: In C
#include<stdio.h>
int max(int a, int b)
{
if(a>b)
return a;
return b;
}
int maxLoot(int hval[], int n)
{
if (n == 0)
return 0;
int value1 = hval[0];
if (n == 1)
return value1;
int value2 = max(hval[0], hval[1]);
if (n == 2)
return value2;
int max_val;
for (int i=2; i<n; i++)
{
max_val = max(hval[i]+value1, value2);
value1 = value2;
value2 = max_val;
}
return max_val;
}
int main()
{
int hval[100],n;
scanf("%d",&n);
for(int i = 0; i <n; i++)
scanf("%d",&hval[i]);
printf("%d",maxLoot(hval, n));
return 0;
}Solution: In Java
import java.util.*;
class Main
{
static int maxLoot(int hval[], int n)
{
if (n == 0)
return 0;
int value1 = hval[0];
if (n == 1)
return value1;
int value2 = Math.max(hval[0], hval[1]);
if (n == 2)
return value2;
int max_val = 0;
for (int i=2; i<n; i++)
{
max_val = Math.max(hval[i]+value1, value2);
value1 = value2;
value2 = max_val;
}
return max_val;
}
public static void main (String[] args)
{
int i;
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int hval[] = new int[50];
for(i=0;i<n;i++)
hval[i] = sc.nextInt();
System.out.println( maxLoot(hval, n));
}
}Solution: In Python 3
def maximize_loot(hval, n):
if n == 0:
return 0
value1 = hval[0]
if n == 1:
return value1
value2 = max(hval[0], hval[1])
if n == 2:
return value2
max_val = None
for i in range(2, n):
max_val = max(hval[i]+value1, value2)
value1 = value2
value2 = max_val
return max_val
hval = []
n = int(input())
hval = list(map(int, input().split()))
n = len(hval)
print( maximize_loot(hval, n))Also Checkout