i am getting WA for this problem..

i think may be i am getting WA for bigger values of h(boundary values)....please help me with this...
left[i] and right[i] record first left/right that is shorter than h[i]

Can you explain your algo?

for each rectangle ,i have stored values of first left and first right rectangle that has height less than this rectangle.
for(int i=1;i < n;i++){
j=i-1;
while(j >=0){
if(h[j] < h[i]) break;
else j=left[j];
}
left[i]=j;
}
similarly for right one.
this part is done using DP.
next step : iterate from i=1 rectangle to i=n-1 and check if the area (right[i]-left[i]-1)*height[i] ) is greater than current value of max.
return max after n iterations.
i think my algo is correct and it is giving correct answer for test cases given ,but dont know why it gives WA

The algorithm you described is correct. The problem is that it seems to have O(N^2) complexity so your program will probably TLE on big test cases. Try imputing big cases around 100000 with all heights equal and check for yourself.

As far as your current problem goes: your program is overflowing. Just try this data:

5 1000000000 1000000000 1000000000 1000000000 1000000000

You should check results bigger than 'int' and 'unsigned' range before submitting. You can just assume it works, since you are mixing 'long long' and 'int' types. The fact that it works for sample input means nothing for most problems.

thanx for replying,
i have changed all unsigned long long to long long int and it is giving correct answer for test case that you gave (5000000000).
but still WA..

You didn't update your code

Here is my code ,

# include<iostream>
//# include<conio.h>
# include<vector>
using namespace std ;
 long long int maxarea1(vector<long long int> h,int n){
    int left[n],right[n],j;
    long long int max,area;
    left[0]=-1;
    right[n-1]=n;
    for(int i=1;i < n;i++){
            j=i-1;
            while(j >=0){
                    if(h[j] < h[i]) break;
                    else j=left[j];
            }
            left[i]=j;
    }
    for(int i=n-2;i >=0;i--){
            j=i+1;
            while(j < n){
                    if(h[j] < h[i]) break;
                    else j=right[j];
            }
            right[i]=j;
    }
    max=h[0];
    for(int i=1;i < n;i++){
            area=(right[i]-left[i]-1)*h[i];
            if(area > max)
                    max=area;
    }
    return max;
};
int main(){
    int n;
    long long int max1;
    long long int x;
    vector<long long int> h;
    scanf("%d",& n);
    while(n){
             for(int i=0;i <n;i++){
                     scanf("%lld",& x); 
                     h.push_back(x);
             }
             max1=maxarea1(h,n);
             printf("%lld\n",max1);
             scanf("%d",& n);
             h.clear();
    }
  //  getch();
    return 0;
}

For this kind of problem it is very easy to make a brute force checker. That is an alternative, much simpler but also much slower, method of solving the problem. You can just check all ranges [a;b] and find the biggest rectangle. Having two methods you can run both of them on some random data and check if solutions match. That is the best way of debugging, much better than just hoping an algorithm works.

thanx for your reply,but this is the only algo that came to my mind and that too after a lot of efforts i put on this problem ,
it would be very helpful if someone can help me finding out the mistake,bcoz i know my code is very close to AC but just a small mistake.
so i dont see any point in thinking again on another logic and code it.
thanx and regards

That's a very bad approach. Coding two algo's is a must. That's pretty much only efficient method of debug for most of the problems. If you won't start applying something like that in your problem solving, you will have a lot of trouble doing problems on your own. Plus brute force algorithms are easy for most of the time, like in this case. You need only O(N^3) algo since it's only for debug not to solve the every test case (only for limited sizes of arrays). You didn't seem to read what I was trying to explain to you in the last post.

Here is my code.I am getting correct output but when i submit it ,it is showing wrong answer.please tell me where is the wrong in my algorithm.
#include <stdio.h>

int MAXSIZE = 200001;
int stack[200001];
int top = -1;

int isempty() {

if(top == -1)
return 1;
else
return 0;
}

int isfull() {

if(top == MAXSIZE)
return 1;
else
return 0;
}

int peek() {
return stack[top];
}

int pop() {
int data;

if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf(“Could not retrieve data, Stack is empty.\n”);
}
}

void push(long long int data) {

if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf(“Could not insert data, Stack is full.\n”);
}
}
int max(int a,int b) {
if (a>b) {
return a;
}
else {
return b;
}
}
void largestarea(long long int a[],long long int n) {
long long int ls[n],rs[n],i;
for (i=0;i<n;i++) {
while (!isempty()) {
if (a[peek()]>=a[i]) {
pop();
}
else {
break;
}
}
if (isempty()) {
ls[i]=0;
}
else {
ls[i]=peek()+1;
}
push(i);
}
while(!isempty()) {
pop();
}
for (i=n-1;i>=0;i–) {
while(!isempty()) {
if (a[peek()]>=a[i]) {
pop();
}
else {
break;
}
}
if (isempty()) {
rs[i]=n-1;
}
else {
rs[i]=peek()-1;
}
push(i);
}
long long int max_area=0;
for (i=0;i<n;i++) {
max_area=max(max_area,a[i]*(rs[i]-ls[i]+1));
}
printf("%lld\n",max_area);
}
int main() {
long long int n,i,t;
while(t–) {
scanf("%lld\n",&n);
long long int a[n];
for (i=0;i<n;i++) {
scanf("%lld",&a[i]);
}
if (a[0]==0) {
return 0;
}
else {
largestarea(a,n);
}
// if (largestarea(a,n)!=0) {
// printf("%lld\n",largestarea(a,n));
// }
// else {
// return 0;
// }
}
}