Hello,
I am getting a TLE for this problem while using an O(n) solution. It computes the maximum rectangle area as it reads the heights. żIs there anything better? Perhaps reading the data and later aplying an O(log n) algorithm, like binary search or some wacky O(1) would do it, but I can't figure them out.
Thank you,
Nov '07
Jun '20
If you have a O( n ) algorithm, probably the bottlenect of your program will be the input reading because it's much slower then simply iterating through the points. Even if you have an O( n lg n ) algorithm, the reading can easily be the slowest part of your program. You probably didn't calculate the complexity right 
Hello,
Thank you all. Zuza, you are right, I didn't calculate the complexity right. My algorithm was really O(n^2). 
Fpavetic, now I know that there is in fact an O(n) algorithm to solve this problem, I'll try to figure it out.
Thank you all again.
I am using an O(n lg n) solution and still get TLE? Should a solution with such complexity exceed the time limit?
NOTE: I am using scanf/printf I/O which I think should be fast..
I am getting WA .
Please tell me the mistakes in my code:
#include <bits/stdc++.h>
using namespace std;
int main(){
long long int n;
long long int a[100005];
while (cin>>n && n!=0){
for(int j=0;j<n;j++){
cin>>a[j];
}
long long int i,area,m=0;
stack< long long int > s;
for( i=0;i<n;){
long long int t=a[i];
if(s.empty() || t>=a[s.top()] ){
s.push(i++);
}
else{
long long int p=s.top();
s.pop();
if(s.empty()){
area=a[p]*i;
}
else{
area=a[p]*(i-s.top()-1);
}
}
m=max(m,area);
}
while (!(s.empty())){
long long int q=s.top();
s.pop();
if(s.empty()) {
area = a[q] *i;
}
else{
area=a[q]*(i-s.top()-1);
}
m=max(m,area);
}
cout<<m<<endl;
}
return 0;
}