Largest Rectangle in Histogram ---WRONG ANS...PLEASE HELP!

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

vectorlft;

vectorrght;

vectorwidth;

vectorarea;

stack<pair<int, int>> s;

int main(){

int arr[] = {6,2,5,4,5,1,6};

int n = sizeof(arr)/sizeof(arr[0]);

int ps = -1;

for(int i=0; i<n; i++){

if(s.size()==0)

{

    lft.pb(ps);

}

else if(s.size()>0 && s.top().first<arr[i]){

    lft.pb(s.top().second);

}

else if(s.size()>0 && s.top().first>=0){

      while(s.size()>0 && s.top().first>=0){

          s.pop();

      }

      if(s.size()==0)

       lft.pb(ps);

      else

        lft.pb(s.top().second); 

}

s.push({arr[i], i});

}

ps = 7;

for(int i=n-1; i>=0; i–){

if(s.size()==0)

{

    rght.pb(ps);

}

else if(s.size()>0 && s.top().first<arr[i]){

    rght.pb(s.top().second);

}

else if(s.size()>0 && s.top().first>=0){

      while(s.size()>0 && s.top().first>=0){

          s.pop();

      }

      if(s.size()==0)

       rght.pb(ps);

      else

        rght.pb(s.top().second); 

}

s.push({arr[i], i});

}

reverse(rght.begin(), rght.end());

for(int i=0; i<n; i++){

width[i] = (rght[i] - lft[i]) - 1;

}

for(int i=0; i<n; i++){

area[i] = width[i]*arr[i];

}

for(int i=0; i<area.size(); i++){

cout << area[i] << " ";

}

}

Please format your code - the forum software has mangled it and it won’t compile! :slight_smile:

4 Likes