SPOJ -  HISTOGRA - Largest Rectangle in a Histogram

Problem link: https://www.spoj.com/problems/HISTOGRA/

IDEA :  For a particular point of the array we need find how much distance to its right and to its left it can take. Actually, we need to find minimum value to its right. To find this we can use stack.if the value of a particular index is less than the previous one which is in stack we need to pop the previous element from the stack and find its total rectangular value.



CODE : 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main()
{
    /*int t,x=0;
    cin>>t;
    */
    while(true)
    {
        ll n;
        cin>>n;
        if(n==0)
            return 0;
        ll a[n+5];
        for(int i=0;i<n;i++)
            cin>>a[i];
        stack <ll> st;
        ll i=0;
        long long mx=0;
        while(i<n)
        {
            if(st.empty()||a[st.top()]<=a[i])
            {
                st.push(i);
                i++;
            }
            else
            {
                ll top =st.top();
                st.pop();
                long long ans= a[top]*(st.empty()? i: i-st.top()-1);
                mx=max(ans,mx);
            }
        }
        while(!st.empty())
        {
            ll top=st.top();
            st.pop();
            long long ans=a[top]*(st.empty() ? i: i-st.top()-1);
            mx=max(ans,mx);
        }
     //cout<<"Case "<<x<<": "<<mx<<endl;
     cout<<mx<<endl;
    }
    return 0;
}