基准时间限制：1 秒 空间限制：131072 KB 分值: 20 

有一个正整数的数组，化为直方图，求此直方图包含的最大矩形面积。例如 2,1,5,6,2,3，对应的直方图如下：

 

 

面积最大的矩形为5,6组成的宽度为2的矩形，面积为10。

 

Input

第1行：1个数N，表示数组的长度(0 <= N <= 50000) 第2 - N + 1行：数组元素A[i]。(1 <= A[i] <= 10^9)

Output

输出最大的矩形面积

Input示例

6

2 1 5 6 2 3

Output示例

10

 

 

//动态规划瞎搞搞就行，要求最大面积，可以枚举以每个小矩形为高的情况，lef[i] 表左边第一个小于 A[i] 的位置，rig 表右，动态规划扫一扫，跳一跳即可

1 #include 
        
          2 using namespace std; 3 #define LL long long 4 #define mkp make_pair 5 #define pr pair
         
           6 #define MX 50005 7  8 int n; 9 int dat[MX];10 int lef[MX];11 int rig[MX];12 13 int main()14 {15     scanf("%d",&n);16     for (int i=1;i<=n;i++)17         scanf("%d",&dat[i]);18 19     for (int i=1;i<=n;i++)20     {21         int k = i-1;22         while (k>0&&dat[i]<=dat[k])23             k = lef[k];24         lef[i]=k;25     }26     for (int i=n;i>=1;i--)27     {28         int k = i+1;29         while (k<(n+1)&&dat[i]<=dat[k])30             k = rig[k];31         rig[i]=k;32     }33     LL ans = 0;34     for (int i=1;i<=n;i++)35     {36         LL temp = ((LL)rig[i]-lef[i]-1)*dat[i];37         ans = max(temp,ans);38     }39     printf("%I64d\n",ans);40     return 0;41 }