Largest Rectangle

Problem Link

<Solution>

#include<bits/stdc++.h>
using namespace std;
int maxhis(int his[],int n)
{
stack<int> s;
int max_area=0;
int tp;
int area_with_top;
int i=0;
while(i<n){
if(s.empty()||his[s.top()]<=his[i])
s.push(i++);
else
{
tp=s.top();
s.pop();
area_with_top=his[tp]*(s.empty()?i:i-s.top()-1);
max_area=max(max_area,area_with_top);

}
}
while(!s.empty())
{
tp=s.top();
s.pop();
area_with_top=his[tp]*(s.empty()?i:i-s.top()-1);
max_area=max(max_area,area_with_top);
}
return max_area;

}
int main()
{
int n,i,area;
cin>>n;
int his[n];
for(i=0;i<n;i++)
cin>>his[i];

cout<<maxhis(his,n)<<endl;
}

#include<bits/stdc++.h>
using namespace std;
int maxhis(int his[],int n)
{
stack<int> s;
int max_area=0;
int tp;
int area_with_top;
int i=0;
while(i<n){
if(s.empty()||his[s.top()]<=his[i])
s.push(i++);
else
{
tp=s.top();
s.pop();
area_with_top=his[tp]*(s.empty()?i:i-s.top()-1);
max_area=max(max_area,area_with_top);

}
}
while(!s.empty())
{
tp=s.top();
s.pop();
area_with_top=his[tp]*(s.empty()?i:i-s.top()-1);
max_area=max(max_area,area_with_top);
}
return max_area;

}
int main()
{
int n,i,area;
cin>>n;
int his[n];
for(i=0;i<n;i++)
cin>>his[i];

cout<<maxhis(his,n)<<endl;
}

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s