Computer Science, asked by YAASI97, 1 year ago

In the strong room of ABC bank there are N vaults arranged in a circle. The amount of money inside each vault displayed on the door. You can empty any number of vaults as long as you do not empty more than 2 out of any 5 adjacent vaults. If you attempt to break more than 2 of any 5 adjacent vaults, an alarm sounds and the sentry a sharp shooter will kill you instantly with his laser gun! Note that as the vaults are arranged in a circle, the last vault is adjacent to the first one.

The output is the maximum amount of money that can be emptied without sounding the alarm

Input Format:

The first line contains an integer N which is the number of vaults. The next line has a sequence of positive integers of length N, giving the amount of cash in its vaults in order

Output Format:

The maximum amount of money that can be looted without sounding the alarm.

Constraints:

N<=50, Amount in each vault <=50000


Example 1

Input 

1000, 2000, 1000, 5000, 9000, 5000, 3000, 4000, 1000

Output
15000

Explanation 
The vaults 1, 5, 6 are looted, giving a total loot of (1000+5000+9000)=15000


Example 2

Input 
10 
1000,2000,3000,5000,9000,7000,6000,4000,7000,5000

Output 
26000

Explanation 
There are 10 vaults arranged in a circle. The amounts in the vaults are 1000, 2000, ... 5000.

One way of getting the maximum is to loot vaults 4, 5, 9 and 10 giving a total of 26000. Hence the output is 26000. Note that no 5 adjacent vaults have more than 2 looted.

Answers

Answered by SamikshaDhere
0

Answer:

The code for above problem in python, C++ and java is as follows.

Explanation:

1. Python

def maxLoot(hval,n):

   if (n < 0):

       return 0

   if (n == 0):

       return hval[0]

   

   pick = hval[n] + maxLoot(hval, n - 2)

   notPick = maxLoot(hval, n - 1)

   return max(pick, notPick)

hval = [ 6, 7, 1, 3, 8, 2, 4 ]

n = len(hval)

print("Maximum loot possible from the valt is : ",maxLoot(hval, n - 1));

2. C++

#include <iostream>

using namespace std;

int maxLoot(int* hval, int n)

{

   if (n < 0) {

       return 0;

   }

   if (n == 0) {

       return hval[0];

   }

   

   int pick = hval[n] + maxLoot(hval, n - 2);

   int notPick  =  maxLoot(hval,  n - 1 );

   return max(pick, notPick);

}

int main()

{

   int hval[] = { 6, 7, 1, 3, 8, 2, 4 };

   int n = sizeof(hval) / sizeof(hval[0]);

   cout << "Maximum loot possible : "

        << maxLoot(hval, n - 1);

   return 0;

}

3. Java

import java.io.*;

class GFG

{

 

 static int maxLoot(int hval[], int n)

 {

   if (n < 0) {

     return 0;

   }

   if (n == 0) {

     return hval[0];

   }

   int pick = hval[n] + maxLoot(hval, n - 2);

   int notPick = maxLoot(hval, n - 1);

   return Math.max(pick, notPick);

 }

 public static void main(String[] args)

 {

   int hval[] = { 6, 7, 1, 3, 8, 2, 4 };

   int n = hval.length;

   System.out.println("Maximum loot value : "

                      + maxLoot(hval, n-1));

 }

}

#SPJ2

Similar questions