2013
12-12

# Largest Rectangle in a Histogram

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.

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 h1, …, hn, where 0 <= hi <= 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.

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.

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

8
4000

http://acm.hdu.edu.cn/showproblem.php?pid=1506

#include <iostream>
using namespace std;

__int64 a[100005];
int r[100005];
int l[100005];

int main()
{
int n,i,k;
while(scanf("%d",&n)!=EOF && n!=0)
{
scanf("%d",&a[1]);
l[0] = 0;
l[1] = 1;
for(i=2;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i] > a[i-1])
l[i] = i;
else
{
k = i;
while(k--)
{
if(a[k] < a[i])
{
l[i] = k+1;
break;
}
else
{
k = l[k];
}
}
}
}
r[n] = n;
for(i=n-1;i>=1;i--)
{
if(a[i] > a[i+1])
r[i] = i;
else
{
k = i;
while((++k) != n+1)
{
if(a[k] < a[i])
{
r[i] = k-1;
break;
}
else
{
k = r[k];
}
}
if(k == n+1)
r[i] = n;
}
}

__int64 max = 0;
for(i=1;i<=n;i++)
{
__int64 ave = (r[i] - l[i] + 1) * a[i];
if(ave > max)
max = ave;
}
printf("%I64d/n",max);
}
return 0;
}

1. 国内的税制，依法交税，死无全尸，所有企业，是所有企业，只要查，肯定有这方面的问题，所以说只要ZF想办你，查帐就能办了你，除非你是友邦外来人士，不然一办一准

2. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环

3. 网站做得很好看，内容也多，全。前段时间在博客园里看到有人说：网页的好坏看字体。觉得微软雅黑的字体很好看，然后现在这个网站也用的这个字体！nice!

4. bottes vernies blanches

I appreciate the efforts you men and women place in to share blogs on such sort of matters, it was certainly useful. Keep Posting!

5. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环

6. #include <cstdio>

int main() {