POJ 2559 Largest Rectangle in a Histogram （DP最大矩形面積）

給定從左到右多個矩形，已知這此矩形的寬度都為1，長度不完全相等。這些矩形相連排成一排，求在這些矩形包括的范圍內能得到的面積最大的矩形，打印出該面積。所求矩形可以橫跨多個矩形，但不能超出原有矩形所確定的范圍。

l[i]表示大於等於h[i]的最左邊的位置，r[i]表示大於等於h[i]的最右邊的位置，這樣可以預處理出l[],r[]，然後ans = max(ans, r[i] - l[i] + 1) * h[i])( 1 <= i <= n).

#include 
#include 
using namespace std;

const int MAXN = 100010;
int l[MAXN], r[MAXN], h[MAXN];

int main()
{
    int n;
    while(cin>>n&&n)
    {
        int i;
        for(i=1; i<=n; ++i)
        {
            scanf("%d", &h[i]);
            l[i]=r[i]=i;
        }

        for(i=2; i<=n; ++i)
            while (l[i] > 1 && h[i] <= h[l[i] - 1])
                l[i] = l[l[i] - 1];
        for(i=n-1; i>=1; --i)
            while (r[i] < n && h[i] <= h[r[i] + 1])
                r[i] = r[r[i] + 1];
        __int64 ans=0;
        for(i=1; i<=n; ++i)
            ans=max(ans, (__int64)(r[i]-l[i]+1)*h[i]);

        cout<