# Thief and Warehouses | Hackerearth practice problem solution

Problem:-

There are N warehouses. The warehouses are located in a straight line and are indexed from 1 to N. Each warehouse contains some number of sacks.

A thief decides to rob these warehouses. Thief figured out that he can escape the police if and only if he follows both the following 2 constraints:

• He will rob only one continuous segment of warehouses.
• He will rob same number of sacks from each warehouse.

Thief wants to calculate the maximum number of sacks he can steal without getting caught by the police.

Input Format:

The first line contains an integer T denoting number test cases.

The first line of each test case contains a single integer N denoting number of warehouses.

The second line of each test case contains N space-separated integers :

$a\left[1\right],a\left[2\right],a\left[3\right]...a\left[n\right].a\left[i\right]$

denotes number of sacks in

${i}_{th}$

warehouse.

Constraints:

• $1<=T<=5$

• $1<=N<={10}^{6}$

• $0<=A\left[i\right]<={10}^{12}$

Output Format:

Output exactly T lines.

The

${i}_{th}$

line should contain a single integer, i.e the answer for

${i}_{th}$

testcase(maximum number of sacks thief can steal without getting caught).

Sample Input
`252 4 3 2 163 0 5 4 4 4 `
Sample Output
`816`
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

In first test case thief will steal 2 sacks from each warehouse from 1 to 4.

$10$

Code:-

you can submit this solution  by using the language c++, c++14 and c++17.

In this solution first three lines of the main function is only for the decreasing the time of execution of the program..
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

This is your choice that you want to use this or not but in some cases the code may take more time in execution and that time we need it .

#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t,n;
cin>>t;
while(t–)
{
cin>>n;
long int a[n];
//taking input
for(int i=0;i<n;i++)
cin>>a[i];
long int total,max=0;
for(int i=0;i<n;i++)
{
long int min=a[i];
total=a[i];
if(min!=0)
{
//if previous value is less than the
// min then we have to also include the
//prevoius value until it less than min
if(a[i]<a[i1] && i!=0)
{
for(int l=i1;l>=0;l–)
{
if(a[l]<min)
break;
total+=min;
}
}
// check form i to last element
// and add it to total until min sacks are
//possible to take from warehouses
for(int j=i+1;j<n;j++)
{
if(a[j]<min)
break;
total+=min;
}
// if max is less total
if(max<total)
max=total;

}
}
cout<<max<<endl;
}
}

Recommended Post:-

MCQs:-