算法-每天一道题（7）-直方图内最大矩形

有一个直方图，用一个整数数组表示，其中每列的宽度为1，求所给直方图包含的最大矩形面积。比如，对于直方图[2,7,9,4],它所包含的最大矩形的面积为14(即[7,9]包涵的7×2的矩形)。
给定一个直方图A及它的总宽度n，请返回最大矩形面积。保证直方图宽度小于等于500。保证结果在int范围内。

测试样例：

[2,7,9,4,1],5

返回：14

C++

class MaxInnerRec {
public:
    int countArea(vector<int> A, int n) {
        int length = 0; // 某个矩形的横向的长度
        int area = 0; // 矩形的面积
        int max = 0; // 最大面积
        for (int i=0; i<n; i++)
        {
            // 往右边扩展，求出此单个柱可以往右边扩展的最大长度
            for (int j=i; j<n; j++)
                if (A[i] > A[j])
                    break;
                else
                    length++;
            // 往左边扩展，求出此单个柱可以往左边扩展的最大长度
            for (int j=i; j>=0; j--)
                if (A[i] > A[j])
                    break;
                else
                    length++;
            length--; // 多加了一次，需要减一
            area = length * A[i];
            if (max < area)
                max = area;
            length = 0;
        }
        return max;
    }
};
/*
解题思路：

求出每个柱状被包括在内的，能够达到的最大面积，
即向右扩展，直到有比它低的，同理向左扩展，求出此面积
*/