Largest Rectangle in a Histogram

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

8
4000

pid=1058" target="_blank">1058 1176 

pid=2870" target="_blank">2870 2571

题目大意：给你一张柱形图，先给你一个N表示柱的数量。然后给你N个高度。每个柱的宽度是1，让你在柱形图中放入一个矩形。要求输出的矩形面积是最大的。

解题思路：矩形的高度一定是那些给出柱的高度中的一个，以一个柱的高度为矩形的高时计算出当前这个高度下最大的矩形面积，枚举每个高度，最后找到那个最大的，
就是 所求。所以题目就变成了在给定高度下找矩形的最大宽度(高度一定找最大面积)，那么就要找到当前高度的左右边界，明显仅仅要旁边的柱比这个高度要高就能够再向旁
边扩展一个单位。解题思路给出。

还好这题没出负数数据，要不然就完蛋了。。。

#include <iostream>
using namespace std;
#define M 100005
__int64 l[M],r[M],vis[M];               //数据用int过不去。所以用__int64.
__int64 max(__int64 x,__int64 y){
    return x>y?x:y;
}
int min(int x,int y){
    return x<y?x:y;
}
__int64 DP(__int64 a[],__int64 n){
    __int64 i;
    for(i=1;i<=n;i++)                //从左边找左边界，从右边開始找会超时，不解释。

    {    
        while(a[i]<=a[l[i]-1])    l[i]=l[l[i]-1];     //假设左边的比当前高度高，说明能够向左边扩展。while这里有点递归的味道。                                                      //直到左边比当前高度低,才结束while。

    }
    for(i=n;i>=1;i--)
    {   
        while(a[i]<=a[r[i]+1])    r[i]=r[r[i]+1];     //找右边界的过程和找左边界过程一样。

    }
    __int64 tot=0;  
    for(i=1;i<=n;i++)                                 //每个高度的最大宽度已经找到，计算最大面积。

    {
        tot=max(tot,(r[i]-l[i]+1)*a[i]);              //宽度为1。所以还要+1.
    }
    return tot;
}

int main(__int64 i,__int64 j,__int64 k)
{
    __int64 n,cur;
    while(scanf("%I64d",&n)!=EOF&&n)
    {  l[0]=l[n+1]=vis[0]=vis[n+1]=-1;               //这里是防一些特殊的数据。按理来说取0就能够了。只是过不了。       r[n+1]=n;                                     
        for(i=1;i<=n;i++)
        { 
            l[i]=r[i]=i;                             //l[i]记录的是vis[i]的左边界，r[i]记录vis[i]的右边界。
            scanf("%I64d",&vis[i]);
        }
        cur=DP(vis,n);
        printf("%I64d\n",cur);
    }
    return 0;
}