Largest Rectangle in a Histogram

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 16152		Accepted: 5218

Description

A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:

Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow n integers h₁,...,h_n, where 0<=h_i<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

8
4000

Hint

Huge input, scanf is recommended.

Source

Ulm Local 2003

/**
链接：http://poj.org/problem?id=2559
思路：大致是dp加上树状数组的原理；
就以该图为例解释：
定义num[i]表示0-i这个范围内的值的个数全加上num[i];
第一个数2直接进栈sta[0] = 2，num[0] = 1;
第二个数1比2小，所以2出栈，因为后面不可能再有数能与2连成一条线上的值2（被1给断开了）；但是2出栈时要与mas比较大小，同时把
2的贡献加给1；此时，sta[0] = 1,num[0] = 2;
继续输入为4，4比1大，进栈，sta[1] = 4,num[1] = 1;
5比4大，进栈，sta[2] = 5;num[2] = 1;
1比5小，5出栈，s=0; s = s + num[2] ;s==1;5*s = 5>mas; mas = 5;
继续1比4小，4出栈，s = s + num[0]; s==2; 所以:4*s = 8>mas; mas = 8;
继续，1与1相等，所以需要合并；sta[0]= 1; num[0] = num[0] + s + 1； num[0] == 5;
其他亦如此；
**/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long sta[100004];
long long num[100004];
int main()
{
    long long n,e;
    while(~scanf("%lld",&n)&&n)
    {
        long long mas = 0, z = 0;
        memset(num,0,sizeof(num));
        for(long long i = 0; i < n; i++){
            scanf("%lld",&e);
            if(i==0){///第一个数，直接进栈；
                sta[z] = e;
                num[z++]=1;
            }else
            {
                long long  s = 0;
                for(long long j = z-1; j >= 0; j--)///对栈进行比较；
                {
                    if(e >= sta[j]) break;///递增，则跳出，该数直接进栈；
                    s = s+num[j];///因为栈里的值是递增的，所以后面的数对前面的数有贡献；
                    mas = max(mas,sta[j]*s);
                    z--;///出栈；
                }
                if(z > 0){///用于合并的判断；
                    if(sta[z-1]==e){
                        num[z-1] = s + 1 + num[z-1];/// +1是输入的值那个数个数多了1；
                    }else{
                        num[z] = s+1;///进栈；
                        sta[z++] = e;
                    }
                }else{
                    num[z] = s+1;///进栈；
                    sta[z++] = e;
                }
            }
        }
        long long s = 0;
        for(long long i = 0; i < z; i++){///找出和；
            s+=num[i];
        }
        for(long long i = 0; i < z; i++){///所有数出栈，并找最大值；
            mas = max(mas,sta[i]*s);
            s = s - num[i];
        }
        printf("%lld
",mas);
    }
    return 0;
}