In this HackerEarth Thief and Warehouses 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:
  1. He will rob only one continuous segment of warehouses.
  2. He will rob a same number of sacks from each warehouse.
The thief wants to calculate the maximum number of sacks he can steal without getting caught by the police.


HackerEarth Thief and Warehouses problem solution


HackerEarth Thief and Warehouses problem solution.

#include<bits/stdc++.h>

#define ll long long
using namespace std;
stack<ll> s;
int main()
{
    int testCases;
    cin>>testCases;
    while(testCases--){
        int n,i;
        scanf("%d",&n);
        ll a[n];
        for(i=0;i<n;i++)
            scanf("%lld",&a[i]);
        ll marea=0,area=0;
        for(i=0;i<n;){
            if(s.empty()||a[s.top()]<=a[i])
                s.push(i++);
            else{
                int tp=s.top();
                s.pop();
                if(s.empty())
                    area=a[tp]*i;
                else
                    area=a[tp]*(i-s.top()-1);
                if(area>marea)
                    marea=area;
            }
        }
        while(!s.empty()){
            int tp=s.top();
                s.pop();
                if(s.empty())
                    area=a[tp]*i;
                else
                    area=a[tp]*(i-s.top()-1);
                if(area>marea)
                    marea=area;
        }
        printf("%lld\n",marea);
    }
}