Header Ads Widget

Thief and Warehouses | Hackerearth practice problem solution


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[1],a[2],a[3]...a[n].a[i] denotes number of sacks in ith warehouse.


  • 1<=T<=5
  • 1<=N<=106
  • 0<=A[i]<=1012

Output Format:

Output exactly T lines.

The ith line should contain a single integer, i.e the answer for ith testcase(maximum number of sacks thief can steal without getting caught).

Sample Input
2 4 3 2 1
3 0 5 4 4 4 
Sample Output
Time Limit: 2
Memory Limit: 256
Source Limit:

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



 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..

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 .

using namespace std;
int main()
    int t,n;
        long int a[n];
        //taking input
        for(int i=0;i<n;i++)
        long int total,max=0;
        for(int i=0;i<n;i++)
            long int min=a[i];
                //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[i-1] && i!=0)
                    for(int l=i-1;l>=0;l--)
                // 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 max is less total

Recommended Post:-


Post a Comment