CCF 201312-3 最大的矩形

试题编号：	201312-3
试题名称：	最大的矩形
时间限制：	1.0s
内存限制：	256.0MB

问题描述：

在横轴上放了n个相邻的矩形，每个矩形的宽度是1，而第i（1 ≤ i ≤ n）个矩形的高度是h_i。这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。

请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是10。

输入格式

　　第一行包含一个整数n，即矩形的数量(1 ≤ n ≤ 1000)。
　　第二行包含n 个整数h₁, h₂, … , h_n，相邻的数之间由空格分隔。(1 ≤ h_i ≤ 10000)。h_i是第i个矩形的高度。

输出格式

　　输出一行，包含一个整数，即给定直方图内的最大矩形的面积。

样例输入

6
3 1 6 5 2 3

样例输出

思路：

1、先把输入的高度值保存到arr数组中，然后遍历数组，假设当前遍历到第i个元素，从第j（j=i+1）个元素开始计算距离s（s=j-i+1）

2、变量low存储从arr[i]到arr[j]个元素间数值最小的元素值

3、计算的面积为(s*low)，每次与最大值ans比较，如果比ans大则更新ans的值

最后输出ans。

#include<iostream>
using namespace std;
int arr[1004];
int main()
{
    int n,ans=-1,low=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    for(int i=0;i<n;i++)
    {
        low=arr[i];
        for(int j=i+1;j<n;j++)
        {
            if(low>arr[j]) low=arr[j];
            int cen=(j-i+1)*low;
            if(cen>ans) ans=cen;
        }
    }
    cout<<ans;
    return 0;
}

大一暑假的时候集训碰到这个题感觉非常的懵逼百度也看不懂

在纸上试着按照别人的代码，把每次遍历的元素都写下来还是不懂

甚至厚着脸皮去qq上问当时带我们集训的一个学长学长还不太想搭理我的样子orz 解释了一下我还是不明白

甚至质疑自己的智商怀疑自己的人生，这题成了我的心里阴影。。

每次看到别人参加什么比赛的时候都会想起来自己实力就是那样，因为自己真的当时努力去尝试理解，还是看不懂，所以甚至对自己的智商产生了质疑。。

现在回想真是非常的愚蠢，其实也不是什么要用到特别难的算法的题目但是自己当时就是无论如何都不能理解这个题

就在昨晚给我想出来了心情非常的复杂。。

笨也没办法啦，慢慢来吧，算是个菜鸟的开头。值得纪念的一题