HISTOGRA : Largest Rectangle in a Histogram

HISTOGRA : Largest Rectangle in a Histogram

Link for the problem: HISTOGRA

SOLUTION:
The hight of rectangles of the histogram is given in the sequence. We have to find the area of the largest possible rectangle in the Histogram. Area of a rectangle is equal to Length*Height.  The height of the largest possible rectangle will be hight of the any given rectangles. So to find the largest possible area, we will find max possible width for every given rectangle. For any given rectangle, when we consider it as forming the largest rectangle, we have to find left limit and right limit up to where the height of the rectangle is less than or equal.
This problem can be solved by using a stack. For every ith rectangle, we have to find left and right index of the rectangle, whose height is less than ith rectangle. Difference between right index and left index will give the possible width for ith rectangle.

IMPLEMENTATION:
Let arr[] be the array of integer denoting heights.
1.) For ith element, if stack is empty push it in the stack.
2.) If stack is not empty, then pop the stack until top is less than ith element. If jth element is popped by ith element then right limit for jth element will be i.
3.) Index of element lying just below ith element in stack will be left limit of ith element.

CODE:

#include <bits/stdc++.h>
#include <stdio.h>
using namespace std;
int main()
{
    while(1)
    {
      long long int n;
      cin>>n;
      if(n==0)
      break;
      long long int a[n],b[n][2],i,j,k;
      for(i=0;i<n;i++)
      {
          cin>>a[i];
          b[i][1]=-1;
      }
      vector<long long int> v;
      v.push_back(0);
      b[0][0]=-1;
      for(i=1;i<n;i++)
      {
          int sz=v.size();
          
          while(sz>=1)
          {
              if(a[i]<a[v[sz-1]])
              {
                  int t;
                  t=v[sz-1];
                  v.pop_back();
                  b[t][1]=i;
                  sz--;
              }
              else
              break;
          }
          if(!v.size())
          {
              b[i][0]=-1;
          }
          else{
              b[i][0]=v[v.size()-1];
          }
          v.push_back(i);
      }
      for(i=0;i<n;i++)
      {
          if(b[i][1]==-1)
          b[i][1]=n;
      }
      long long int max=0,p;
      for(i=0;i<n;i++)
      {
            p=a[i]*(b[i][1]-b[i][0]-1);
            if(max<p)
            max=p;
      }
      printf("%lld\n",max);
      
    }
    return 0;

}