1 / 12
Nov 2007

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,

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 smile

Hello,

Thank you all. Zuza, you are right, I didn't calculate the complexity right. My algorithm was really O(n^2). blush 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..

2 years later

What are the possible locations for the smallest inp within the largest rectangle?

s.top().first > inp[i]
The lowest inp in largest rectangle is at its left end, isnt it?

Is it?
6 2 1 1 1 1 1

10 years later

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;

}