Maximum Area Histogram (MAH)

PHOTO EMBED

Tue Jun 21 2022 14:13:52 GMT+0000 (Coordinated Universal Time)

Saved by @Ranjan_kumar #c++

vector<int>left;
stack<pair<int,int>>s;
int pseudo_index=-1;
for(int i=0;i<n;i++)
  {
    if(s.size()==0)
      {
        left.push_back(pseudo_index);
      }
    else if(s.size()>0 && s.top().first<arr[i])
      {
        left.push_back(s.top());
      }
    else if(s.size()>0 && s.top().first>=arr[i])
      {
        while(s.size()>0 && s.top().fisrt>=arr[i])
          {
            s.pop();
          }
        if(s.size()==0)
          left.push_back(s.top().second);
      }
    s.push(arr[i];)
  }
return left;               //NSL completed

vector<int>right;          //NSR doing
stack<pair<int,int>>s2;
int pseudo_index=7;
for(int i=size-1;i>=0;i--)
  {
    if(s2.size()==0)
      {
        right.push_back(pseudo_index);
      }
    else if(s2.size()>0 && s2.top().first<arr[i])
      {
        right.push_back(s.top());
      }
    else if(s2.size()>0 && s2.top().first>=arr[i])
      {
        while(s2.size()>0 && s2.top().fisrt>=arr[i])
          {
            s2.pop();
          }
        if(s2.size()==0)
          right.push_back(s2.top().second);
      }
    s2.push(arr[i];)
  }
reverse (right.begin(),right.end());
return right;           //NSR completed
 

for(int i=0;i<size;i++)
  {
    width[i]=right[i]-left[i]-1;
  }
for(int i=0;i<size;i++){
  area[i]=arr[i]*width[i];
}
return max of area[i];       //final answer
content_copyCOPY

https://www.youtube.com/watch?v=J2X70jj_I1o&list=PL_z_8CaSLPWdeOezg68SKkeLN4-T_jNHd&index=7